# How to disprove that every odd number can be written in the form $2^n + p$ with $p$ prime?

How can I disprove that every odd number, $2k+1>1$ can be written in the form $2k+1 = 2^n + p$ with $p$ prime?

I know it's not true but I don't know how to explain that it is not true.

• You just need a single counterexample – Casper Feb 6 '17 at 5:31
• Did you try the first few odd numbers? (3,5,7,...) – Isomorphism Feb 6 '17 at 5:36
• What is the domain for $n$? If $n>0$ consider the mighty number $3$. – Adam Hughes Feb 6 '17 at 5:36
• In case anyone is curious about trying the first several values, it is becoming tedious to continue: 3=1+2, 5=2+3, 7=4+3, 9=4+5, 11=8+3, 13=8+5, 15=8+7, 17=4+13, 19=16+3, 21=16+5, 23=16+7, 25=8+17, 27=8+19, 29=16+13, 31=8+23, ... – JMoravitz Feb 6 '17 at 5:38
• This is the problem that led Erdos to invent covering congruences. – Gerry Myerson Feb 6 '17 at 6:21

A brief spreadsheet search on the primes gives $149$ as a counterexample.

$149-2^0 = 148$, even
$149-2^1 = 147 = 3\cdot7^2$
$149-2^2 = 145 = 5\cdot29$
$149-2^3 = 141 = 3\cdot47$
$149-2^4 = 133 = 7\cdot19$
$149-2^5 = 117 = 3^2\cdot13$
$149-2^6 = 85 = 5\cdot17$
$149-2^7 = 21 = 3\cdot7$

The smallest composite counterexample is $905$, the first member of the OEIS A098237.

It suffices to find a counterexample.

After some searching, we find A133122

Odd numbers which cannot be written as the sum of an odd prime and a power of two

$$1, 3, 127, 149, 251, 331, 337, 373, 509, 599, 701,\dots$$

Even allowing $$n=0$$ and the use of even primes to say $$3=2^0+2$$ and ignoring $$1$$, the smallest counterexample is apparently $$127$$.

To prove that $$127$$ is in fact a counterexample, note that $$127 = 64+3^2\cdot 7 = 32+5\cdot 19 = 16 + 3\cdot 37 = 8+7\cdot 17=\dots$$ and so no power of two is valid.

These numbers are named Obstinate Numbers.