Whether a Prime number can be written as sum of a Prime number and $2^n$?

Whether a Prime number greater than can be written as sum of a Prime number and $2^n$?

$P_2 = P_1 + 2^N$

Some Examples of this
$3=2+2^0$

$5=3+2^1$

$1021=509+2^9$

-

1 Answer

No, this is not true, as you can discover by looking at the number 127. It cannot be expressed in the required form, and I believe there are more examples.

Edit: Another example is 331, since it is prime, yet all the numbers $331-2^n$ are composite for $n=1, 2, \dots 8$.

Editt:

There is a paper available online by Zhi-Wei Sun in which he gives some background and further examples, and the amazing statement that the integer

$$M = 47867742232066880047611079$$

plus or minus a power of $2$ can never be a prime, although I am not sure if $M$ is itself a prime (although my computer thinks it is likely to be).

-
So reverse of it also won't be true for some numbers right? $P_2$=$P_1$-$2^n$ –  Shan Jan 3 '13 at 11:00
There's many more examples here: oeis.org/A065381 –  Douglas S. Stones Jan 3 '13 at 11:01
@Old John That's pretty interesting fact about that integer. –  Shan Jan 3 '13 at 11:29
@Shan Apparently that fact was "observed" by Cohen and Selfridge in 1975. I strongly recommend a read of the paper by Zhi-Wei Sun. –  Old John Jan 3 '13 at 11:40
Sure will do that –  Shan Jan 3 '13 at 11:45