Dual Riesel problem

jasong · 2006-11-02, 04:19

I've been told(they might be wrong) that another equivalent to the Riesel conjecture(For k*2^n-1 k=509203 is the smallest k for which n always yields a composite) is the dual Riesel conjecture(same thing, but the formula is 2^n-k.)

I was wondering if there was a legal(I can't use Primo legally) way to check a k/n pair of that form for primality without taking an overly long amount of time.

Thanks in advance.

philmoore · 2006-11-02, 16:34

Do probable prime tests first, which will eliminate the vast majority of composites. Perhaps if you have some interesting probable primes, someone on the forum who can legally run Primo might check some candidates for you.

ET_ · 2006-11-02, 19:28

Quote:

Originally Posted by philmoore

Do probable prime tests first, which will eliminate the vast majority of composites. Perhaps if you have some interesting probable primes, someone on the forum who can legally run Primo might check some candidates for you.

Sure...

jasong · 2006-11-02, 21:55

2^690-9221
2^72-23669
2^1428-23669
2^153-26773
2^60-31859
2^133-38473
2^493-38473
2^51-40597
2^135-40597
2^361-46663
2^83-67117
2^146-81041
2^360-93839
2^480-93839
2^528-93839
2^1080-93839
2^140-97139
2^1451-107347
2^81-113983
2^273-113983
2^329-113983
2^585-113983
2^1905-113983
2^179-114487
2^219-114487
2^539-114487
2^40-121889
2^1328-121889
2^122-141941
2^314-141941
2^638-146561
2^520-161669
2^1178-162941
2^224-191249
2^182-192971
2^61-215443
2^1221-215443
2^37-226153
2^1909-226153
2^97-234343
2^337-234343
2^1090-245561
2^47-250027
2^42-252191
2^60-273809
2^456-273809
2^121-275293
2^1069-275293
2^1741-275293
2^684-315929
2^884-315929
2^306-319511
2^1170-319511
2^50-324011
2^554-324011
2^49-325123
2^265-325123
2^1524-336839
2^69-342673
2^405-342673
2^1628-353159
2^72-362609
2^128-362609
2^457-364903
2^312-365159
2^912-365159
2^1552-365159
2^1624-365159
2^214-368411
2^96-402539
2^496-402539
2^588-402539
2^37-409753
2^61-409753
2^343-415267
2^431-415267
2^887-415267
2^1231-415267
2^63-450457
2^303-450457
2^511-450457
2^895-450457
2^1732-469949
2^129-470173
2^381-470173
2^633-470173
2^46-474491
2^358-474491
2^718-474491
2^958-474491
2^1758-474491
2^291-485557
2^1911-485557
2^83-485767
2^105-494743
Thanks in advance :)

paulunderwood · 2006-11-02, 22:28

Jason, all these numbers can be shown to be prime (or not) using Pari/GP function isprime(). I've just tried the largest and it took about 2 seconds on a Pentium 4 2.4Ghz using half its CPU resources...

philmoore · 2006-11-02, 22:42

Has some program such as pfgw said that these are all probable primes? Actually, I would think that pfgw would be able to show that most are actually prime, not just probable prime. Another possibility is Tony Forbes' VFYPR, which uses the APRCL algorithm, although I have not used it:
http://www.ltkz.demon.co.uk/ar2/vfypr.htm
He says that numbers up to around 3300 digits may be tested with it.

This dual Riesel project is something that I think Payam Samidoost was interested in, but I don't think he ever got a web-page for it off the ground. Of course, only one prime is needed for each k to eliminate it. Of the 69 remaining k's how many have no known dual prime?

jasong · 2006-11-03, 23:34

Quote:

Originally Posted by philmoore

This dual Riesel project is something that I think Payam Samidoost was interested in, but I don't think he ever got a web-page for it off the ground. Of course, only one prime is needed for each k to eliminate it. Of the 69 remaining k's how many have no known dual prime?

Attempting to find "dual" primes for the last 69 k's is my goal. Probably won't prove anything, but it's fun to try.

MooooMoo · 2007-03-02, 18:14

Quote:

Originally Posted by philmoore

This dual Riesel project is something that I think Payam Samidoost was interested in, but I don't think he ever got a web-page for it off the ground. Of course, only one prime is needed for each k to eliminate it. Of the 69 remaining k's how many have no known dual prime?

Check out this site: http://sierpinski.insider.com/riesel

It hasn't been updated for years, though.

jasong · 2007-03-03, 03:13

Here are my results for the left over ks:

Code:

123547 2^7-123547
342847 tested to 100000----------------------------sieved 100K-500K
397027 2^19-397027 
444637 tested to 10000-------------------------------
2293   tested to 100000-------------------------- 
9221   2^6-9221
23669  2^72-23669(pr)(testing)(prime)
26773  2^9-26773
31859  2^12-31859
38473  2^133-38473(pr)(prime)
40597  2^15-40597
46663  2^361-46663(pr)(testing)(prime)
65531  2^16-65531
67117  2^83-67117(pr)(prime)
74699  2^2372-74699(pr)(prime)
81041  2^26-81041
93839  2^360-93839(pr)(prime)
97139  2^20-97139
107347 2^3-107347
113983 2^81-113983
114487 2^3-114487
121889 2^8-121889
129007 2^7-129007
141941 2^2-141941 
143047 2^2267-143047(pr)(prime)
146561 2^638-146561(pr)(prime)
161669 2^520-161669(pr)(prime)
162941 2^2-162941
191249 2^224-191249(pr)(prime)
192971 2^182-192971
196597 tested to 100000-------------------------------
206039 2^8-206039
206231 2^22-206231
215443 2^61-215443(pr)(prime)
226153 2^37-226153(pr)(prime)
234343 2^1-234343
245561 2^1090-245561(pr)(prime)
250027 2^47-250027(pr)(prime)
252191 2^42-252191(pr)(prime)
273809 2^12-273809
275293 2^25-275293
304207 tested to 100000----------------------------------
315929 2^684-315929(pr)(prime)
319511 2^18-319511
324011 2^14-324011
325123 2^49-325123(pr)(prime)
327671 2^2-327671
336839 2^4-336839
342673 2^69-342673(pr)(prime)
344759 tested to 100000---------------------------------
353159 2^1628-353159(pr)(prime)
362609 2^8-362609
363343 2^13957-363343(pr)====================================================
364903 2^457-364903(pr)(prime)
365159 2^16-365159
368411 2^22-368411
371893 2^21-371893
384539 2^32672-384539(pr)================================================
386801 tested to 100000-----------------------------
398023 2^21-398023
402539 2^28-402539
409753 2^37-409753(pr)(prime)
415267 2^343-415267(pr)(prime)
428639 2^8684-428639(pr)(testing in 2)
450457 2^63-450457(pr)(prime)
469949 2^1732-469949(pr)(prime)
470173 2^21-470173
474491 2^46-474491
477583 2^5-477583
485557 2^291-485557
485767 2^11-485767
494743 2^105-494743
502573 2^13-502573

I don't think it's worthwhile to test any further, unless you simply want to find probable primes. Maybe I'm wrong, but I don't think it's possible to test these numbers except in their "general" form. If I'm wrong, someone please post.

sweety439 · 2020-06-03, 17:00

Quote:

Originally Posted by jasong

Here are my results for the left over ks:

Code:

123547 2^7-123547
342847 tested to 100000----------------------------sieved 100K-500K
397027 2^19-397027 
444637 tested to 10000-------------------------------
2293   tested to 100000-------------------------- 
9221   2^6-9221
23669  2^72-23669(pr)(testing)(prime)
26773  2^9-26773
31859  2^12-31859
38473  2^133-38473(pr)(prime)
40597  2^15-40597
46663  2^361-46663(pr)(testing)(prime)
65531  2^16-65531
67117  2^83-67117(pr)(prime)
74699  2^2372-74699(pr)(prime)
81041  2^26-81041
93839  2^360-93839(pr)(prime)
97139  2^20-97139
107347 2^3-107347
113983 2^81-113983
114487 2^3-114487
121889 2^8-121889
129007 2^7-129007
141941 2^2-141941 
143047 2^2267-143047(pr)(prime)
146561 2^638-146561(pr)(prime)
161669 2^520-161669(pr)(prime)
162941 2^2-162941
191249 2^224-191249(pr)(prime)
192971 2^182-192971
196597 tested to 100000-------------------------------
206039 2^8-206039
206231 2^22-206231
215443 2^61-215443(pr)(prime)
226153 2^37-226153(pr)(prime)
234343 2^1-234343
245561 2^1090-245561(pr)(prime)
250027 2^47-250027(pr)(prime)
252191 2^42-252191(pr)(prime)
273809 2^12-273809
275293 2^25-275293
304207 tested to 100000----------------------------------
315929 2^684-315929(pr)(prime)
319511 2^18-319511
324011 2^14-324011
325123 2^49-325123(pr)(prime)
327671 2^2-327671
336839 2^4-336839
342673 2^69-342673(pr)(prime)
344759 tested to 100000---------------------------------
353159 2^1628-353159(pr)(prime)
362609 2^8-362609
363343 2^13957-363343(pr)====================================================
364903 2^457-364903(pr)(prime)
365159 2^16-365159
368411 2^22-368411
371893 2^21-371893
384539 2^32672-384539(pr)================================================
386801 tested to 100000-----------------------------
398023 2^21-398023
402539 2^28-402539
409753 2^37-409753(pr)(prime)
415267 2^343-415267(pr)(prime)
428639 2^8684-428639(pr)(testing in 2)
450457 2^63-450457(pr)(prime)
469949 2^1732-469949(pr)(prime)
470173 2^21-470173
474491 2^46-474491
477583 2^5-477583
485557 2^291-485557
485767 2^11-485767
494743 2^105-494743
502573 2^13-502573

I don't think it's worthwhile to test any further, unless you simply want to find probable primes. Maybe I'm wrong, but I don't think it's possible to test these numbers except in their "general" form. If I'm wrong, someone please post.

Are there any newer status (or any large (probable) primes) of this problem? e.g. for the dual Sierpinski problem, there are many large (probable) primes:

Code:

2^16389+67607
2^21954+77899
2^22464+63691
2^24910+62029
2^25563+22193
2^26795+57083
2^26827+77783
2^28978+34429
2^29727+20273
2^31544+19081
2^33548+ 4471
2^38090+47269
2^56366+39079
2^61792+21661
2^73360+10711
2^73845+14717
2^103766+17659
2^104095+7013
2^105789+48527
2^139964+35461
2^148227+60443
2^176177+60947
2^304015+64133
2^308809+37967
2^551542+19249
2^983620+60451
2^1191375+8543
2^1518191+75353
2^2249255+28433
2^4583176+2131
2^5146295+41693
2^9092392+40291

sweety439 · 2020-06-03, 17:04

Also, should we allow negative primes? If so, then the smallest remain k is 2293, otherwise, it is 1871.

2006-11-02, 04:19	#1
jasong "Jason Goatcher" Mar 2005 110110110011₂ Posts	Dual Riesel problem I've been told(they might be wrong) that another equivalent to the Riesel conjecture(For k*2^n-1 k=509203 is the smallest k for which n always yields a composite) is the dual Riesel conjecture(same thing, but the formula is 2^n-k.) I was wondering if there was a legal(I can't use Primo legally) way to check a k/n pair of that form for primality without taking an overly long amount of time. Thanks in advance.

2006-11-02, 22:28	#5
paulunderwood Sep 2002 Database er0rr 2·3·739 Posts	Jason, all these numbers can be shown to be prime (or not) using Pari/GP function isprime(). I've just tried the largest and it took about 2 seconds on a Pentium 4 2.4Ghz using half its CPU resources... Last fiddled with by paulunderwood on 2006-11-02 at 22:29

2006-11-02, 22:42	#6
philmoore "Phil" Sep 2002 Tracktown, U.S.A. 1120₁₀ Posts	Has some program such as pfgw said that these are all probable primes? Actually, I would think that pfgw would be able to show that most are actually prime, not just probable prime. Another possibility is Tony Forbes' VFYPR, which uses the APRCL algorithm, although I have not used it: http://www.ltkz.demon.co.uk/ar2/vfypr.htm He says that numbers up to around 3300 digits may be tested with it. This dual Riesel project is something that I think Payam Samidoost was interested in, but I don't think he ever got a web-page for it off the ground. Of course, only one prime is needed for each k to eliminate it. Of the 69 remaining k's how many have no known dual prime? Last fiddled with by philmoore on 2006-11-02 at 22:43

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
The dual Sierpinski/Riesel problem	sweety439	sweety439	15	2022-01-26 23:43
The reverse Sierpinski/Riesel problem	sweety439	sweety439	20	2020-07-03 17:22
Dual Sierpinski/Riesel prime	sweety439	sweety439	0	2016-12-07 15:01
Fun with the SOB and Riesel Sieve problem	jasong	jasong	1	2007-07-23 06:29
P4 dual core problem	tholloway	Hardware	5	2006-10-28 20:16

2006-11-02, 16:34	#2
philmoore "Phil" Sep 2002 Tracktown, U.S.A. 2⁵·5·7 Posts	Do probable prime tests first, which will eliminate the vast majority of composites. Perhaps if you have some interesting probable primes, someone on the forum who can legally run Primo might check some candidates for you.

2006-11-02, 21:55	#4
jasong "Jason Goatcher" Mar 2005 3×7×167 Posts	2^690-9221 2^72-23669 2^1428-23669 2^153-26773 2^60-31859 2^133-38473 2^493-38473 2^51-40597 2^135-40597 2^361-46663 2^83-67117 2^146-81041 2^360-93839 2^480-93839 2^528-93839 2^1080-93839 2^140-97139 2^1451-107347 2^81-113983 2^273-113983 2^329-113983 2^585-113983 2^1905-113983 2^179-114487 2^219-114487 2^539-114487 2^40-121889 2^1328-121889 2^122-141941 2^314-141941 2^638-146561 2^520-161669 2^1178-162941 2^224-191249 2^182-192971 2^61-215443 2^1221-215443 2^37-226153 2^1909-226153 2^97-234343 2^337-234343 2^1090-245561 2^47-250027 2^42-252191 2^60-273809 2^456-273809 2^121-275293 2^1069-275293 2^1741-275293 2^684-315929 2^884-315929 2^306-319511 2^1170-319511 2^50-324011 2^554-324011 2^49-325123 2^265-325123 2^1524-336839 2^69-342673 2^405-342673 2^1628-353159 2^72-362609 2^128-362609 2^457-364903 2^312-365159 2^912-365159 2^1552-365159 2^1624-365159 2^214-368411 2^96-402539 2^496-402539 2^588-402539 2^37-409753 2^61-409753 2^343-415267 2^431-415267 2^887-415267 2^1231-415267 2^63-450457 2^303-450457 2^511-450457 2^895-450457 2^1732-469949 2^129-470173 2^381-470173 2^633-470173 2^46-474491 2^358-474491 2^718-474491 2^958-474491 2^1758-474491 2^291-485557 2^1911-485557 2^83-485767 2^105-494743 Thanks in advance :)

2020-06-03, 17:04	#11
sweety439 "99(4^34019)99 palind" Nov 2016 (P^81993)SZ base 36 2²×919 Posts	Also, should we allow negative primes? If so, then the smallest remain k is 2293, otherwise, it is 1871.