2^k - 2m+1 = prime: (Was: Sum Of Primes Is Power Of Primes: Question)

[David Wilson]

There is no prime of the form

    p = 2^k - 777149

p will be divisible by

d  =
    3   if k == 1 (mod 2)
    5   if k == 2 (mod 4)
    7   if k == 4 (mod 12)
   13  if k == 8 (mod 12)
   19  if k == 12 (mod 36)
   37  if k == 0 (mod 36)
   73  if k == 24 (mod 36)

You can prove that for every k >= 0, d exists and is a proper divisor of p.
Therefore A096502(388575) does not exist as currently defined.

The analysis of these numbers (p = 2^k - n) is much like the analysis of the
Sierpinski (p = 2^n k + 1) or Riesel (p = 2^n k - 1) numbers. The way we
prove that a prime of the form exists is to find one, the way we prove it
does not exist is to find a sequence of divisors of p periodic in k. If we
can't find periodic divisors, a probabilistic argument says there should be
a prime with probability 1, but that's not proof, of course.

It is conjectured that 78557 and 509203 are the smallest Sierpinski and
Riesel numbers, respectively, since these are the smallest for which it
seems likely that periodic divisors exist. However, there are smaller 
numbers
that have stubbornly refused to yield up primes, despite the strenuous
computational efforts of "Seventeen or Bust" and "The Riesel Project".

I suspect the same will be true for this problem.  I will offhandedly
conjecture that 388575 is the smallest value for which A096502 is truly
undefined, but I would be amazed if we were able to establish
A096502(n) for all smaller n.

If you had said 2^k+(2n-1) instead of 2^k-(2n-1), then

    2^n + 78557

is always composite. Amazingly, but not coincidentally, 78557 is also the
smallest Sierpinsky number, such that

    78557*2^n + 1

always composite. Grind on that one for a bit.


----- Original Message ----- 
From: "Leroy Quet" <q1qq2qqq3qqqq at yahoo.com>
To: <seqfan at ext.jussieu.fr>
Cc: <q1qq2qqq3qqqq at yahoo.com>; <qq-quet at mindspring.com>
Sent: Sunday, April 06, 2008 5:46 PM
Subject: 2^k - 2m+1 = prime: (Was: Sum Of Primes Is Power Of Primes: 
Question)


>
> --- Leroy Quet <q1qq2qqq3qqqq at yahoo.com> wrote:
>
> I wrote in part:
>>...
>> For these sequences to be infinite, a necessary
>> (unless forbidden m's are never obtained) but
>> not
>> sufficient condition is that there is always at
>> least one prime p equal to:
>>
>> p = 2^k - m