[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