OPEN
This is open, and cannot be resolved with a finite computation.
Let $A$ be the set of all odd integers not of the form $p+2^{k}+2^l$ (where $k,l\geq 0$ and $p$ is prime). Is the upper density of $A$ positive?
In
[Er77c] Erdős credits Schinzel with proving that there are infinitely many odd integers not of this form, but gives no reference. Crocker
[Cr71] has proved there are $\gg\log\log N$ such integers in $\{1,\ldots,N\}$. Pan
[Pa11] improved this to $\gg_\epsilon N^{1-\epsilon}$ for any $\epsilon>0$. Erdős believed this cannot be proved by covering systems, i.e. integers of the form $p+2^k+2^l$ exist in every infinite arithmetic progression.
The sequence of such numbers is
A006286 in the OEIS.
See also
[10],
[11], and
[16].
This is discussed in problem A19 of Guy's collection
[Gu04].
View the LaTeX source
This page was last edited 28 September 2025.
Additional thanks to: Ralf Stephan
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #9, https://www.erdosproblems.com/9, accessed 2025-12-07
