Is every large odd integer the sum of a squarefree number and a power of 2? (Erdős #11)
Statement
Is every sufficiently large odd integer $n$ the sum of a squarefree number and a power of $2$? That is, for all large odd $n$, do there exist a squarefree integer $s$ (no prime square divides $s$) and an integer $k\geq 0$ with $n=s+2^k$? Erdős also often asked the same question under the weaker assumption that $n$ is merely not divisible by $4$.
Acceptance. FULLY RESOLVES: a complete proof that every sufficiently large odd integer is the sum of a squarefree number and a power of 2 — machine-checkable (Lean/Coq) preferred, else a full written proof; if the proof yields an explicit threshold, close the remaining range by computation shipped with code and an exhaustiveness certificate. OR a disproof: a proof that infinitely many odd integers are not so representable (an explicit infinite family with proof; note a single sporadic exception does not settle the 'sufficiently large' form, though any verified exception below the background's verified bound would falsify that record and must be reported). ADVANCES: (a) extend the exhaustive verification strictly beyond the bound stated in the background, with reproducible code and an exhaustiveness certificate; (b) a full proof of the two-powers-of-2 variant (every large odd $n=s+2^j+2^k$ with $s$ squarefree), which Erdős considered possibly easy; (c) a quantitative strengthening of the almost-all result with an explicit exceptional-set bound, with proof; (d) a proof of the variant for all $n$ not divisible by 4, or new unconditional consequences sharpening the Wieferich-prime connection stated in the background. Deliver the proof file, or the verification code + attained bound + certificate.
Background
A problem Erdős returned to repeatedly ([Er77c], [Er80, p.96], [ErGr80, p.28], [Er85c], [Er90], [Er92c], [Er97], and more); mentioned as problem A19 of Guy's collection [Gu04]; listed as open on erdosproblems.com/11 (fetched 2026-07-13, status 'open', tagged 'number theory | additive basis'). Verification record: Odlyzko checked it up to $10^7$, and Hercher [He24b] has verified it for all odd integers up to $2^{50}\approx 1.12\times 10^{15}$. Granville and Soundararajan [GrSo98] proved the problem is closely tied to Wieferich primes (primes $p$ with $2^{p-1}\equiv 1\pmod{p^2}$, OEIS A001220): 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 — so a full proof would carry significant unconditional consequences. Erdős could prove the statement holds (with a single power of 2) for almost all odd $n$, and thought the variant allowing TWO powers of 2 is 'perhaps easy' (still unproven per the page). Related problems on the site: Erdős #9, #10, #16 (erdosproblems.com/9, /10, /16); the venue's problem on the density of odd integers not of the form $p+2^k+2^l$ (Erdős #9) is a close neighbor from the same family, but a distinct question. A formalized statement exists in google-deepmind/formal-conjectures; OEIS A377587 is also linked from the page. The attacker's tool: a sieve-accelerated verification run pushing the exhaustive bound past $2^{50}$ (for each odd $n$, test $n-2^k$ for squarefreeness with wheel/precomputed square-divisibility sieves), or an attack on the two-powers-of-2 variant, where Erdős expected an accessible proof.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #11 (T. F. Bloom) | website |
| REF-02 | OEIS A001220 — Wieferich primes: primes p with 2^(p-1) == 1 (mod p^2) | website |
| REF-03 | OEIS A377587 — smallest odd m with m-2^k not squarefree for all 1<=k<=n (tracks this conjecture) | website |
| REF-04 | Formalized statement of Erdős #11 (google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.