There are infinitely many odd numbers not expressible as the sum of a prime number and a power of $2$ Prove that there are infinitely many odd integers that are not expressible as the sum of a prime number and a power of two.
This is a difficult problem. Please give me some hints and some examples of this.
 A: Erdos proved this in the paper in which he introduced the concept of covering congruences. The reference is On integers of the form $2^n+ p$  and some related problems, Summa Brasil Math 11(1950), 1-11. The proof is given by Fabrykowski and Smotzer, Covering systems of congruences, Math Mag 78 (2005) 228-231, available at http://www.maa.org/sites/default/files/3004416309960.pdf.bannered.pdf
EDIT. The Erdos paper is available at http://www.renyi.hu/~p_erdos/1950-07.pdf. Some of it is heavy going, but the part that answers the question here is Theorem 3 and its proof, which is quite elementary. http://www.renyi.hu/~p_erdos/ has the collected papers of Erdos. 
A: Below is the key passage from the paper Gerry linked to.
If $k$ is a nonnegative integer, then at least one of the following congruences holds:
$$
\begin{aligned} 
2^k&\equiv1\pmod3,\\ 
2^k&\equiv1\pmod7,\\ 
2^k&\equiv2\pmod5,\\ 
2^k&\equiv8\pmod{17},\\ 
2^k&\equiv2^7\pmod{13},\\
2^k&\equiv2^{23}\pmod{241}.
\end{aligned}
$$
[JL:
This is easy to see by checking, case-by-case, that irrespective of the residue class of $k$ modulo $24$ at least one of the above congruences holds. Observe that $2$ is of order $12$ modulo $13$ and of order $24$ modulo $241$. The authors of that paper did it by first observing that the relevant residue classes modulo $2,3,4,8,12$ and $24$ cover all the integers.]
Now 
consider 
the 
congruences 
$1\pmod3$, 
$1 
\pmod 
7$, 
$2 
\pmod 
5$, 
$8 
\pmod 
{17}$, 
$2^7 
\pmod 
{13}$, 
and 
$2^{23} 
\pmod 
{241}$. 
Since 
the 
moduli 
are 
pairwise 
relatively 
prime, 
there 
are 
infinitely 
many 
integers 
that 
satisfy 
all 
the 
congruences, 
by 
virtue 
of 
the 
Chinese 
Remainder 
Theorem. 
Now, 
if 
an 
odd 
integer 
$a$ 
satisfies 
all 
the 
congruences, 
then 
all 
the 
integers 
of 
the 
form 
$a-2^k$
are 
divisible 
by 
one 
of 
the 
moduli 
$3, 
7, 
5, 
17, 
13 $
or 
$241.$ 
It 
follows 
that 
$a-2^k$
is 
not 
prime 
and 
therefore 
$a$ 
does 
not 
have 
the 
form 
$a=2^k+p$.
A: There are many related results to this problem about expressing integers as the sum of some number of primes and sum number of powers of two. 
This problem was originally a conjecture of de Polignac that every sufficiently large odd integer may be expressed as $p + 2^v$. Romanoff showed that a positive proportion of the odd integers may be expressed as such, however van der Corput showed that the exceptions formed a set of positive density (!). Finally, Erdos exhibited an arithmetic progression which are all exceptions, as shown in the top answer.
As for similar conjectures, Gallagher proved that the density of odd integers which may be written as
$$p + 2^{\nu_1} + \dots + 2^{\nu_r}$$
for $r \leq k$ tends to $1$ as $k \to \infty$. This result is quite old and am not sure what progress there has been since.
