# Can I express any odd number with a power of two minus a prime?

I have been running a computer program trying to see if I can represent any odd number in the form of

$$2^a - b$$

With b as a prime number. I have seen an earlier proof about Cohen and Selfridge regarding odd numbers that are nether a sum or a difference of a power of two and a prime, and I was curious to see if anyone has found an odd number that couldn't be represented using the above formula.

-

Fred Cohen and J. L. Selfridge, Not Every Number is the Sum or Difference of Two Prime Powers contains an example of such a number:

Corollary: 47867742232066880047611079 is prime and neither the sum nor difference of a power of two and a prime.

-

Erdos's argument essentially gives that there is an infinite arithmetic progression of odd numbers containing no element of the form power of two minus a prime.

Define

\begin{array}{cccc} i & a_i & m_i & p_i \\ 1 & 1 & 2 & 3 \\ 2 & 2 & 4 & 5 \\ 3 & 4 & 8 & 17 \\ 4 & 8 & 16 & 257 \\ 5 & 16 & 32 & 65537 \\ 6 & 0 & 64 & 641 \\ 7 & 32 & 64 & 6700417 \\ \end{array}

Set $A_0=\{x:x\equiv 1 \pmod{8}\}$, $A_i=\{x:x\equiv 2^{a_i} \pmod{p_i}\}$ ($1\leq i\leq 7$), $B=A_0\cap A_1\cap\cdots\cap A_7$.

$B$ is an AP consisting of odd numbers. Assume that $x\in B$ and $x=2^n-q$ for some odd prime $q$. For some $1\leq i\leq 7$, we have $n\equiv a_i \pmod{m_i}$, therefore $x\equiv 2^{a_i}-q \pmod{p_i}$. As $x\in A_i$, we also have $x\equiv 2^{a_i} \pmod{p_i}$, consequently $q=p_i$. But this is impossible as $2^n\equiv 0 \pmod{8}$ for $n\geq 3$, $p_i\equiv 1,3,5 \pmod{8}$ and as $x\in A_0$, $x\equiv 7 \pmod{8}$.

-
This argument comes from the paper in which Erdos introduced covering congruences to an unsuspecting world. – Gerry Myerson Jan 5 '14 at 16:19
This made me wonder, does anyone actually know the smallest odd positive number that cannot be written in the form $2^a-p$. Using covering congruences I can proof that 509203 cannot be written the form $2^a-p$. But I suspect there might be smaller numbers that cannot be written in the form $2^a-p$. If a number is not of the form $2^a-p$ can one always use a covering congruences argument to prove this? – Maarten Derickx Jan 6 '14 at 10:19