15
$\begingroup$

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.

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
35
$\begingroup$

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.

Improve this answer
$\endgroup$
0
14
$\begingroup$

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}$.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ This argument comes from the paper in which Erdos introduced covering congruences to an unsuspecting world. $\endgroup$
    – Gerry Myerson
    Commented Jan 5, 2014 at 16:19
  • $\begingroup$ 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? $\endgroup$
    – Maarten Derickx
    Commented Jan 6, 2014 at 10:19
  • $\begingroup$ @Maarten (if you're still here), you may be interested in Riesel numbers, en.wikipedia.org/wiki/Riesel_number $\endgroup$
    – Gerry Myerson
    Commented Jul 15, 2018 at 12:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .