Problem 236

Erdős Problem #236: declared status 'open'. Formalized: yes. 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)$? Current best: 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$. Prize: no. OEIS: A039669, A109925. Tags: number theory, primes.