8
$\begingroup$

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.

$\endgroup$
6
  • 4
    $\begingroup$ You just need a single counterexample $\endgroup$ – Casper Feb 6 '17 at 5:31
  • 2
    $\begingroup$ Did you try the first few odd numbers? (3,5,7,...) $\endgroup$ – Isomorphism Feb 6 '17 at 5:36
  • $\begingroup$ What is the domain for $n$? If $n>0$ consider the mighty number $3$. $\endgroup$ – Adam Hughes Feb 6 '17 at 5:36
  • $\begingroup$ 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, ... $\endgroup$ – JMoravitz Feb 6 '17 at 5:38
  • $\begingroup$ This is the problem that led Erdos to invent covering congruences. $\endgroup$ – Gerry Myerson Feb 6 '17 at 6:21
5
$\begingroup$

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.

$\endgroup$
11
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.