 mersenneforum.org even ks and the Riesel Conjecture
 Register FAQ Search Today's Posts Mark Forums Read  2007-10-07, 06:01 #1 jasong   "Jason Goatcher" Mar 2005 5×701 Posts even ks and the Riesel Conjecture I'm sure most of you are familiar with the Riesel Conjecture. It states that 509203 is believed to be the lowest odd k where the equation k*2^n-1 is always composite for all n from 1 to infinity. In other words if you take 509203*2^n-1, you can plug in any integer for n, from 1 to infinity, and it will always be composite. But the conjecture only involves odd k. What about the even numbers? There are almost certainly odd ks that already have a prime found, but that the n-value is so low that there are even multiples that don't have a prime attached to them. Here's what I propose. (The following is why it's in the programming forum) Download pfgw if you don't have it and use it to test all odd k from 1 to 254601.(a little less than half of 509203, 254601.5 happens to be exactly half) You only have to do it for n's from 1 to 18 for this first pass, any higher and all even multiples are covered, so a prime wouldn't matter. Weed out all the values that don't have a prime attached them, maybe make a new file for them. Then test those k-values for n=19 to 10,000. Make a file that contains the values that weren't found prime for either pass. After that, you can either continue to try and find primes for these numbers, or you can send the file to me. Anybody want to try this?   2007-10-07, 06:07 #2 paulunderwood   Sep 2002 Database er0rr 65648 Posts If k==2^r*a where a is odd then k*2^n+1 == a*2^(n+r)+1 Last fiddled with by paulunderwood on 2007-10-07 at 06:29   2007-10-07, 20:57   #3
jasong

"Jason Goatcher"
Mar 2005

5·701 Posts Quote:
 Originally Posted by paulunderwood If k==2^r*a where a is odd then k*2^n+1 == a*2^(n+r)+1 I realize that, although you express it much better than I would have. The reason for not using that fact is that I'm asking other people to do my work, so I think I'm better off manually analyzing the resulting files than asking someone to do something that seems to be a lot more intricate than my present request.   2007-10-08, 09:39 #4 paulunderwood   Sep 2002 Database er0rr 1101011101002 Posts My point is that only odd "k" needs to be studied. Your above method of using PFGW can be done a lot more quickly with the scripting language behind PFGW or maybe with an ABC2 file -- both of which I am rusty on now. Still, I can see no reason to study even "k" edit: For the "Riesel's Problem", I should have said: "If k==2^r*a where a is odd then k*2^n-1 == a*2^(n+r)-1" (with a greater than 1.) Let me spell it out for you: 509203*2^n-1 == 509203*2*2^(n-1)-1 == 118406*2^(n-1)-1 Now rewrite this as: 118406*2^m-1 where m=n-1 Here you have your even k == 118406 and your exponent is "m". HTH Last fiddled with by paulunderwood on 2007-10-08 at 09:57   2007-10-08, 12:42 #5 Jens K Andersen   Feb 2006 Denmark 2·5·23 Posts jasong is considering even k for which k*2^n-1 is never prime for positive n. 17861*2^2-1 = 71444-1 is prime, so 17861 is not a Riesel number. 71444*2^n-1 gives the same prime for n = 0, but it's composite for 1 <= n <= 50000. So 71444 is currently a candidate for the smallest even k. If we allowed n=0 then we could multiply by 2: 142888*2^n-1 is the same prime for n = -1, but composite for 0 <= n <= 50000. The following assumes only positive n is allowed. With PARI/GP and PFGW I have identified 9 even candidate k which are below 509203 and not a multiple of a smaller even or odd candidate: 71444, 94604, 154334, 340934, 347174, 351134, 381854, 449564, 478214. I haven't completely verified whether there are more than the 9. The 9 primes below 509203 which eliminate 9 smaller odd k in the Riesel problem: 17861*2^2-1 23651*2^2-1 77167*2^1-1 170467*2^1-1 173587*2^1-1 175567*2^1-1 190927*2^1-1 112391*2^2-1 239107*2^1-1 None of them has another prime with exponent below 30000, and none of them has a prime in the Prime Pages database. The first 5 have currently also been tested to 50000. The largest prime found in my small search is 6869*2^45084-1. It eliminated the even candidate 6869*2^4 = 109904, where 6869*2^4-1 is prime.   2007-10-08, 14:26 #6 jasong   "Jason Goatcher" Mar 2005 66618 Posts There we go, I guess I just didn't explain it well enough. Now that we've got something started, I'm going to set up a thread in the "Other Projects" forum. Anything that involves programming and this project goes here, stuff about running it on a computer goes here. Btw, Jens(sorry about the use of the first name, Jennifer is a feminine name, but I'm really not sure if Jens is a shorter version of Jennifer, so I'm not certain of your gender. Don't worry, it's the cloak of the Internet, not your looks :) ) could you send me the stuff you've done so far? I could do the manual work and post in the other thread, linked in this post. Last fiddled with by jasong on 2007-10-08 at 14:49 Reason: Added link then the last paragraph   2007-10-08, 17:47 #7 Jens K Andersen   Feb 2006 Denmark 3468 Posts Jens is male (and if you care about Danish pronunciation then it's like yens). I have completed the testing of even k candidates which are below 509203 and are not a power of 2 times a smaller odd or even candidate. There are only the 9 earlier reported which correspond to these odd k: 17861, 23651, 77167, 170467, 173587, 175567, 190927, 112391, 239107. All 9 have been tested to k*2^50000-1. I don't want to coordinate or participate in a search above 50000. I have not sieved above 50000. It would probably be best to sieve all 9 at the same time if there is an appropriate sieve. The smallest proven odd k is 509203 so there is no prime of form (2*509203)*2^n-1. Note that I have only looked for even k candidates below 509203 and not examined even k from 509203 to 2*509203.   2007-10-08, 17:52 #8 paulunderwood   Sep 2002 Database er0rr 1101011101002 Posts Thanks, Jens, for the clarification. I apologize that I did not understand that the minimal even "k" solution of this Riesel type problem, as posed by Jason, was sought. Presumable, some effort will be put into the Sierpinski side of this problem too Last fiddled with by paulunderwood on 2007-10-08 at 17:56   2007-10-14, 19:27 #9 Jean Penné   May 2004 FRANCE 24×5×7 Posts Even Sierpinski problem and Fermat primes I was looking at even k candidates for the Sierpinski problem. With a little program using the "calc" interpreter by Bell and Noll, I searched for even k values < 78557, giving no primes for n=1 to 4096. There are 89 k values remaining, and beetween them, the value k=65536... k+1 = 65537 = F4 is prime, indeed, but if I do not accept the exponent n=0, I may remark that 65536 is even, less than 78557, and can only be eliminated as a Sierpinski candidate if there is at least one Fermat number greater than F4 beeing prime, but most Mathematicians are thinking it is unlikely... Whatever F4 is, or is not the largest Fermat prime, if we accept the even Sierpinki candidates, we can assert : F4 is the largest Fermat prime --------> The Sierpinski conjecture is false. I hope this remark would interest you... Regards, Jean Last fiddled with by Jean Penné on 2007-10-14 at 19:32 Reason: To correct a logical error...   2007-10-15, 02:41 #10 philmoore   "Phil" Sep 2002 Tracktown, U.S.A. 22×32×31 Posts I wonder if you would mind posting the 89 remaining candidates?   2007-10-15, 05:48   #11
Jean Penné

May 2004
FRANCE

24×5×7 Posts Here are the remaining ones :

Quote:
 Originally Posted by philmoore I wonder if you would mind posting the 89 remaining candidates?
Oh yes, it is not a secret :
k = 766
k = 1532
k = 3064
k = 5794
k = 6122
k = 6128
k = 9694
k = 10594
k = 10718
k = 11588
k = 11794
k = 12244
k = 12256
k = 12638
k = 14026
k = 14986
k = 15302
k = 15914
k = 16846
k = 17086
k = 19388
k = 20446
k = 21188
k = 21436
k = 23176
k = 23588
k = 24488
k = 24512
k = 25276
k = 27574
k = 28052
k = 28054
k = 29972
k = 30604
k = 31828
k = 32296
k = 33634
k = 33692
k = 34172
k = 36214
k = 36406
k = 38498
k = 38776
k = 40892
k = 41702
k = 42334
k = 42362
k = 42376
k = 42872
k = 43606
k = 45398
k = 46352
k = 47176
k = 47558
k = 48976
k = 49024
k = 49474
k = 50552
k = 50678
k = 51638
k = 51722
k = 55148
k = 55306
k = 55816
k = 55846
k = 56104
k = 56108
k = 56866
k = 59944
k = 61208
k = 63656
k = 64322
k = 64592
k = 64786
k = 65536
k = 67268
k = 67322
k = 67384
k = 68344
k = 69422
k = 69998
k = 72428
k = 72812
k = 73562
k = 73966
k = 75122
k = 76996
k = 77552
k = 78158
89 ks remaining

Moreover, I already eliminated the first five ones :

766*2^6392+1 is prime! Time: 88.832 ms.
1532*2^6391+1 is prime! Time: 131.564 ms.
3064*2^6390+1 is prime! Time: 133.993 ms.
5794*2^9714+1 is prime! Time: 449.787 ms.
6122*2^33287+1 is prime! Time: 3.431 sec.

In fact, 766, 1532, 3064 and 6122 yield the same prime, and so, we can
also eliminate the other multiples of these numbers by powers of 2 :

12244, 24488, 48976, and also :
11588, 23176, 46352

I will contnue now!

Jean   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post rogue Conjectures 'R Us 36 2018-01-03 19:53 em99010pepe Sierpinski/Riesel Base 5 8 2010-06-08 21:21 Primeinator Information & Answers 12 2009-07-19 23:30 jasong Conjectures 'R Us 39 2008-04-06 00:21 jasong Information & Answers 1 2006-10-06 06:17

All times are UTC. The time now is 06:33.

Fri Oct 23 06:33:35 UTC 2020 up 43 days, 3:44, 0 users, load averages: 1.78, 1.81, 1.72