Odlyzko has checked this up to $10^7$. Hercher [He24b] has verified this is true for all odd integers up to $2^{50}\approx 1.12\times 10^{15}$.

Granville and Soundararajan [GrSo98] have proved that this is very related to the problem of finding Wieferich primes, which are $p$ for which $2^{p-1}\equiv 1\pmod{p^2}$ - for example, if every odd integer is the sum of a squarefree number and a power of $2$ then a positive proportion of primes are non-Wieferich primes.


Erdős often asked this under the weaker assumption that $n$ is not divisible by $4$. Erdős thought that proving this with two powers of 2 is perhaps easy, and could prove that it is true (with a single power of two) for almost all $n$.

See also [9], [10], and [16].

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

View the LaTeX source

This page was last edited 07 October 2025.