# 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. Jan 5, 2014 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? Jan 6, 2014 at 10:19
• @Maarten (if you're still here), you may be interested in Riesel numbers, en.wikipedia.org/wiki/Riesel_number Jul 15, 2018 at 12:35