  Let $\mathcal{U}$ be the set of positive odd integers that cannot be
represented as the sum of a prime and a power of two. In this paper, we prove
that $\mathcal{U}$ is not a union of finitely many infinite arithmetic
progressions and a set of asymptotic density zero. This gives a negative answer
to a conjecture of P. Erd\H os. We pose several problems and a conjecture for
further research.
