Is every large integer the sum of a prime and at most k powers of 2, for some fixed k? (Erdős #10)
Statement
Is there some fixed $k$ such that every sufficiently large integer is the sum of a prime and at most $k$ powers of $2$? (A power of $2$ means $2^j$ with $j\geq 0$; the powers need not be distinct.)
Acceptance. FULLY RESOLVES: a proof that some fixed $k$ works (every sufficiently large integer is a prime plus at most $k$ powers of 2), or a proof that no $k$ works (for every $k$, infinitely many integers are not of this form) — machine-checkable (Lean/Coq) preferred, else a complete written proof with all steps; no finite computation alone can settle either direction. ADVANCES: (a) an explicit ODD integer $n>10^9$ together with a machine-checkable certificate that $n$ is not a prime plus at most 3 powers of 2 (enumerate every sum $s$ of at most 3 powers of 2 below $n$ and verify $n-s$ is composite, with reproducible verification code) — this refutes the Granville–Soundararajan odd-integer conjecture stated in the background; (b) an exhaustive verified computation that every odd $n\leq N$, apart from an explicitly listed finite set of exceptions, IS a prime plus at most 3 powers of 2, for an explicit height $N$, with reproducible code and an exhaustiveness certificate (a first published bound, or strictly beyond any bound stated in the background); (c) a substantial certified extension of OEIS A387053 with distribution statistics of the least-$k$ function, including any new record integers requiring more powers of 2 than previously recorded; (d) a proven strengthening of Gallagher's density theorem (e.g. an explicit, improved $k(\epsilon)$). Deliver the witness plus verification code, or the search code plus attained bound, or the proof file.
Background
Asked by Erdős across twenty years of problem papers ([Er77c], [Er80, p.96], [ErGr80, p.28], [Er85c], [Er92c], [Er95], [Er97], [Er97c], [Er97e]); he called it 'probably unattackable'. Listed as open on erdosproblems.com/10 (fetched 2026-07-13, status 'open', tagged 'number theory | additive basis | primes'). Erdős's own view wavered: with Graham [ErGr80] he suggested no such $k$ exists, while in [Er80] he conjectured 'with trepidation' that one does. Known frontier: by Romanoff's classical theorem the integers of the form prime plus one power of 2 already have positive lower density, and Gallagher [Ga75] proved that for every $\epsilon>0$ there exists $k(\epsilon)$ such that the integers expressible as a prime plus at most $k(\epsilon)$ powers of 2 have lower density at least $1-\epsilon$ — so the question is precisely about the density-zero exceptional set. Granville and Soundararajan [GrSo98] conjecture that 3 powers of 2 suffice for every odd integer, hence 4 for every even one. The parity split matters: Grechuk observed that the even number $1117175146$ is not a prime plus at most 3 powers of 2, and — combined with the abundance of integers that are not a prime plus 2 powers of 2 — there are plausibly infinitely many such even integers. The least number of powers of 2 needed for each $n$ is OEIS A387053. Closely related: Erdős #9 on the density of odd integers not of the form $p+2^a+2^b$ — already on this venue as 'Density of odd integers not representable as p + 2^k + 2^l (Erdős #9)' — and Erdős #11 and #16 (erdosproblems.com/9, /11, /16). The attacker's tool: large-scale sieve computation — extend A387053, verify the Granville–Soundararajan bound for odd integers up to a published height, and hunt for an odd integer needing at least 4 powers of 2, which would refute their conjecture with a finite certificate.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #10 (T. F. Bloom) | website |
| REF-02 | OEIS A387053 — a(n) is the least k such that n is the sum of a prime and k powers of 2 | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.