Problem Statement
For any $d\geq 1$ and $k\geq 0$ let $P(d,k)$ be the set of integers which are the sum of distinct powers $d^i$ with $i\geq k$. Let $3\leq d_1<d_2<\cdots <d_r$ be integers such that\[\sum_{1\leq i\leq r}\frac{1}{d_r-1}\geq 1.\]Can all sufficiently large integers be written as a sum of the shape $\sum_i c_ia_i$ where $c_i\in \{0,1\}$ and $a_i\in P(d_i,0)$?
If we further have $\mathrm{gcd}(d_1,\ldots,d_r)=1$ then, for any $k\geq 1$, can all sufficiently large integers be written as a sum of the shape $\sum_i c_ia_i$ where $c_i\in \{0,1\}$ and $a_i\in P(d_i,k)$?
If we further have $\mathrm{gcd}(d_1,\ldots,d_r)=1$ then, for any $k\geq 1$, can all sufficiently large integers be written as a sum of the shape $\sum_i c_ia_i$ where $c_i\in \{0,1\}$ and $a_i\in P(d_i,k)$?
Categories:
Number Theory Base Representations Complete Sequences
Progress
The second question was conjectured by Burr, Erdős, Graham, and Li [BEGL96], who proved it for $\{3,4,7\}$.The first question was asked separately by Erdős in [Er97] and [Er97e] (although there is some ambiguity over whether he intended $P(d,0)$ or $P(d,1)$ - certainly he mentions no gcd condition). A simple positive proof of the first question was provided (and formalised in Lean) by Aristotle thanks to Alexeev; see the comments for details.
In [BEGL96] they record that Pomerance observed that the condition $\sum 1/(d_i-1)\geq 1$ is necessary (for both questions), but give no details. Tao has sketched an explanation in the comments. It is trivial that $\mathrm{gcd}(d_1,\ldots,d_r)=1$ is a necessary condition in the second question.
Melfi [Me04] gives a construction, for any $\epsilon>0$, of an infinite set of $d_i$ for which every sufficiently large integer can be written as a finite sum of the shape $\sum_i c_ia_i$ where $c_i\in \{0,1\}$ and $a_i\in P(d_i,0)$ and yet $\sum_{i}\frac{1}{d_i-1}<\epsilon$.
See also [125].
Source: erdosproblems.com/124 | Last verified: January 13, 2026