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 [b]odd[/b] 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 [b]odd[/b] 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 [b]those[/b] 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?

If k==2^r*a where [I]a[/I] is odd then k*2^n+1 == a*2^(n+r)+1 :whistle:

[QUOTE=paulunderwood;115841]If k==2^r*a where [I]a[/I] is odd then k*2^n+1 == a*2^(n+r)+1 :whistle:[/QUOTE]
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.

My point is that only odd "k" needs to be studied. :wink:

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" :grin:

edit: For the "Riesel's Problem", I should have said:
"If k==2^r*a where [I]a[/I] is odd then k*2^n-1 == a*2^(n+r)-1" (with [I]a[/I] 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

jasong is considering even k for which k*2^n-1 is never prime for [B]positive[/B] 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.

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 [url=http://www.mersenneforum.org/showthread.php?p=115921#post115921]here.[/url]

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.

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.

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 :smile:

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

I wonder if you would mind posting the 89 remaining candidates?

Here are the remaining ones :
 

[QUOTE=philmoore;116357]I wonder if you would mind posting the 89 remaining candidates?[/QUOTE]

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

Okay, these have been eliminated by the work of 17-or-bust:

k = 9694 (4847)
k = 19388 (4847)
k = 38776 (4847)
k = 77552 (4847)
k = 10718 (5359)
k = 21436 (5359)
k = 42872 (5359)
k = 38498 (19249)
k = 76996 (19249)
k = 55306 (27653)
k = 38498 (19249)
k = 56866 (28433)

Similarly, we know there is no prime known for the following because 17-or-bust (and others) have failed to find a prime for the corresponding odd k:

k = 20446 (10223)
k = 40892 (10223)
k = 42362 (21181)
k = 45398 (22699)
k = 49474 (24737)
k = 67322 (33551)

6128 is the continuation of 766, 1532, 3064 rather than 6122, so this eliminates 12256, 24512, and 49024 as well. I'll bet we can eliminate most of the rest of these with the list of primes at:
[url]http://www.prothsearch.net/sierp.html[/url]
as there are a number of primes there with n values > 50,000.