mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2007-10-07, 06:01   #1
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

350510 Posts
Default 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?
jasong is offline   Reply With Quote
Old 2007-10-07, 06:07   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

5×17×37 Posts
Default

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
paulunderwood is offline   Reply With Quote
Old 2007-10-07, 20:57   #3
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

5·701 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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.
jasong is offline   Reply With Quote
Old 2007-10-08, 09:39   #4
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

5×17×37 Posts
Default

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
paulunderwood is offline   Reply With Quote
Old 2007-10-08, 12:42   #5
Jens K Andersen
 
Jens K Andersen's Avatar
 
Feb 2006
Denmark

E616 Posts
Default

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.
Jens K Andersen is offline   Reply With Quote
Old 2007-10-08, 14:26   #6
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

5×701 Posts
Default

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
jasong is offline   Reply With Quote
Old 2007-10-08, 17:47   #7
Jens K Andersen
 
Jens K Andersen's Avatar
 
Feb 2006
Denmark

2×5×23 Posts
Default

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.
Jens K Andersen is offline   Reply With Quote
Old 2007-10-08, 17:52   #8
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

61118 Posts
Default

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
paulunderwood is offline   Reply With Quote
Old 2007-10-14, 19:27   #9
Jean Penné
 
Jean Penné's Avatar
 
May 2004
FRANCE

2×52×11 Posts
Default 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...
Jean Penné is offline   Reply With Quote
Old 2007-10-15, 02:41   #10
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

111610 Posts
Default

I wonder if you would mind posting the 89 remaining candidates?
philmoore is offline   Reply With Quote
Old 2007-10-15, 05:48   #11
Jean Penné
 
Jean Penné's Avatar
 
May 2004
FRANCE

2×52×11 Posts
Default Here are the remaining ones :

Quote:
Originally Posted by philmoore View Post
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

11 k's are already dead...

I will contnue now!

Jean
Jean Penné is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Untested Riesel conjectures sorted by conjecture rogue Conjectures 'R Us 36 2018-01-03 19:53
Riesel Base 5 LLR em99010pepe Sierpinski/Riesel Base 5 8 2010-06-08 21:21
Riesel primes Primeinator Information & Answers 12 2009-07-19 23:30
even ks and the Riesel Conjecture jasong Conjectures 'R Us 39 2008-04-06 00:21
Question about Riesel and Sierpinski conjecture. jasong Information & Answers 1 2006-10-06 06:17

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

Mon Apr 6 06:45:51 UTC 2020 up 12 days, 4:18, 1 user, load averages: 1.22, 1.34, 1.33

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.