Problem Statement
Is there some $k$ such that every integer is the sum of a prime and at most $k$ powers of 2?
Categories:
Number Theory Additive Basis Primes
Progress
Conjecture
Erdos and Graham suggest no such universal $k$ exists.
Key Result
Gallagher: For any $\epsilon > 0$, there exists $k(\epsilon)$ such that integers representable as prime + $\leq k(\epsilon)$ powers of 2 have density $> 1-\epsilon$.
Counterexample: $1117175146$ cannot be expressed as prime + at most 3 powers of 2.
Related
- Related: Problems #9, #11, #16
Source: erdosproblems.com/10 | Last verified: January 13, 2026