Problem Statement
Let $f(n)$ count the number of solutions to $n=p+2^k$ for prime $p$ and $k\geq 0$. Is it true that $f(n)=o(\log n)$?
Categories:
Number Theory Primes
Progress
Erdős [Er50] proved that there are infinitely many $n$ such that $f(n)\gg \log\log n$.Erdős could not even prove that there do not exist infinitely many integers $n$ such that for all $1< 2^k<n$ the number $n-2^k$ is prime - he conjectured (see problem A19 of Guy's collection [Gu04]) that\[4,7,15,21,45,75,105\]are the only such $n$. This is A039669 in the OEIS. Mientka and Weitzenkamp [MiWe69] have proved there are no other such $n\leq 2^{44}$.
Vaughan [Va73] has proved that the number of $n\leq N$ such that $n-2^k$ is prime for all $2^k<n$ is\[< \exp\left(-c\frac{\log \log \log N}{\log\log N}\log N\right)N\]for some constant $c>0$.
The sequence of values of $f(n)$ is A109925 on the OEIS.
See also [237].
Source: erdosproblems.com/236 | Last verified: January 14, 2026