OPEN
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)$?
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 (probably $n=105$ is the largest such integer).
The sequence of values of $f(n)$ is A109925 on the OEIS.
See also [237].
