The only known such $n$ are\[4,7,15,21,45,75,105.\]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 $1<2^k<n$ is\[< \exp\left(-c\frac{\log \log \log N}{\log\log N}\log N\right)N\]for some constant $c>0$.

This is discussed in problem A19 of Guy's collection [Gu04].

Erdős made the stronger conjecture (see [236]) that that number of $1<2^k<n$ for which $n-2^k$ is prime is $o(\log n)$.

View the LaTeX source

This page was last edited 23 January 2026.