[seqfan] Re: Somebody knows this conjecture?

David Wilson davidwwilson at comcast.net
Sun Jan 16 03:53:34 CET 2011


Let r be the Riesel number 509203, which happens also to be prime.

To show that r is Riesel, we first prove that for any integer n,

     [1]   2^n * r - 1 == 0 (mod p(n))

where prime p(n) is a prime in P = {3, 5, 7, 13, 17, 241}. For negative n, 
we use the
modular interpretation of 2^-n. p(n) is the period-24 function on the 
integers

    3, 5, 3, 241, 3, 5, 3, 13, 3, 5, 3, 7, 3, 5, 3, 17, 3, 5, 3, 13, 3, 5, 
3, 7

For n >= 0, we have 2^n * r - 1 >= r - 1 > 241 >= p(n), so p(n) is a proper 
divisor of
2^n * r - 1, which must be composite. We conclude r is Riesel.

Replacing n with -n in [1] gives

    2^-n * r - 1 == 0 (mod p(-n))

and a little arithmetic yields

    2^n - r == 0 (mod p(-n))

So p(-n) is a divisor of 2^n - r.

We now show that p = r is a counterexample to the "p + q = 2^n" conjecture. 
Suppose there exists
prime q with r + q = 2^n for some n. Since q is prime, we have

    q > 0  ==>  2^n - r > 0  ==>  2^n - 509203 > 0  ==>  n >= 19.

This means

    2^n - r > 2^19 - r = 15085 > 241 >= p(-n).

So p(-n) is a proper divisor of 2^n - r, implying 2^n - r is composite. This 
answers your question
from the quoted message.

Since q = 2^n - r is composite, there is no prime q satisfying r + q = 2^n, 
refuting the "p + q = 2^n"
conjecture.


An analogous argument goes through for almost every prime Riesel number r. 
The argument could fail
if 2^n - r = p(-n) for some n, in which case 2^n - r is prime. However, it 
is much more likely (read
almost certain) that we will find 2^n - r > p(-n) for all n with 2^n > r (as 
we found with r = 509203),
giving 2^n - r composite for all n. This most, if not all, primes in A101306 
should be counterexample p
values in the p + q = 2^n conjecture.



The smallest proven Riesel number is 509203. The Riesel Sieve Project at

        http://www.primegrid.com/forum_thread.php?id=1731&nowrap=true#21625

is attempting to show 509203 is the smallest by finding primes of the form 
2^n * r + 1 for all r < 509203.
However, there are few candidate r values that have so far resisted 
elimination.

Since the Riesel problem and the "p + q = 2^n" problem are sister problems, 
we should expect that if it
is hard to eliminate a Riesel candidate r, it should be likewise hard to 
satisfy r + q = 2^n with q prime
for that r.

If we look at the link above, we see that the smallest uneliminated Riesel 
candidate is r = 2293.
And if we look a few seqfan posts back, we find RGWv trying to solve p + q = 
2^n:

>    In the first 1000 primes, I have found values for all terms but 4;
> unknown values at: 286, 341, 530 & 591 and they exceed 35000. I will let
> this run over night. I will be sending into the OEIS a b-text file 
> tomorrow.
>
> Bob.

Not coincidentally, one of Bob's problematic primes is p(341) = 2293.

----- Original Message ----- 
From: "T. D. Noe" <noe at sspectra.com>
To: <davidwwilson at comcast.net>
Sent: Saturday, January 15, 2011 3:30 PM
Subject: [seqfan] Re: Somebody knows this conjecture?


> At 11:54 PM -0500 1/14/11, David Wilson wrote:
>>The conjecture is false.
>>
>>For p = 509203, we have p+q = 2^n => q is divisible by one of 3, 5, 7, 13,
>>17 or 241.
>>
>>Any other prime in A101306 is also a counterexample.
>>
>>In fact, this problem is the Riesel problem in disguise.
>
>
> I'm feeling sort of dense.  How does this follow?
>
> 509203*2^n - 1 is composite for all n
>
> implies that
>
> 2^n - 509203 is composite for all n?
>
> Thanks,
>
> Tony
>
>
>
> -----
> No virus found in this message.
> Checked by AVG - www.avg.com
> Version: 10.0.1191 / Virus Database: 1435/3382 - Release Date: 01/15/11
> 



-----
No virus found in this message.
Checked by AVG - www.avg.com
Version: 10.0.1191 / Virus Database: 1435/3382 - Release Date: 01/15/11




More information about the SeqFan mailing list