OPEN
This is open, and cannot be resolved with a finite computation.
Let $A$ be the set of all odd integers $\geq 1$ 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?
The open status of this problem reflects the current belief of the owner of this website. There may be literature on this problem that I am unaware of, which may partially or completely solve the stated problem. Please do your own literature search before expending significant effort on solving this problem. If you find any relevant literature not mentioned here, please add this in a comment.
Crocker
[Cr71] proved that there are infinitely many odd integers not of this form; his proof in fact proves 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.
In
[Er80] Erdős conjectured 'with some trepidation' that for any finite set of primes $P$ all large integers $n$ can be written as $n=m+2^k+2^l$ where $m$ is a multiple of one of the primes in $P$.
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 07 April 2026. View history
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 2026-05-21
