OPEN This is open, and cannot be resolved with a finite computation.
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)$?
Disclaimer: The open status of this problem reflects the current belief of the owner of this website. There may be literature on this problem that I am unaware of, which may partially or completely solve the stated problem. Please do your own literature search before expending significant effort on solving this problem. If you find any relevant literature not mentioned here, please add this in a comment.
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].
This page was last edited 01 December 2025.
External data from the database - you can help update this
Formalised statement?
Yes
Additional thanks to: Boris Alexeev, Alfaiz, Dustin Mixon, and Terence Tao
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #124, https://www.erdosproblems.com/124, accessed 2025-12-14
-
In [BEGL96], the problem is formulated in a way that only allows powers of $d_i$ greater than $d_i^0 = 1$ to be added. However, in [Er97] and [Er97e], it's formulated so that $1$s are allowed. Incidentally, this means that all the proofs in [BEGL96] actually prove slightly stronger statements.
-
[Note: this comment was written before 2025/12/01, when the problem text was updated.]
Aristotle from Harmonic has solved this problem all by itself, working only from the formal statement! Type-check it online!
A formal statement of the conjecture was available in the Formal Conjectures project. Unfortunately, there is a typo in that statement, wherein the comment says $\geq 1$ in the display-style equation while the corresponding Lean says "= 1". (That makes the statement weaker.) Accordingly, I have also corrected that issue and included a proof of the corrected statement. Finally, I removed a lot of what I believed were unnecessary aspects of the statement, and Aristotle proved that too. In the end, there are three different versions proven, of which this is my favorite:
theorem erdos_124 : ∀ k, ∀ d : Fin k → ℕ,
(∀ i, 2 ≤ d i) → 1 ≤ ∑ i : Fin k, (1 : ℚ) / (d i - 1) →
∀ n, ∃ a : Fin k → ℕ,
∀ i, ((d i).digits (a i)).toFinset ⊆ {0, 1} ∧
n = ∑ i, a i
I believe this is a faithful formalization of (a strengthening of) the conjecture stated on this page.As mentioned by DesmondWeisenberg above, there's an issue involving the power 1 (which corresponds to the units digit here) that means the conjecture in [BEGL96] differs from this. I believe the version in [Er97] matches the statement here, in part because it lacks a gcd condition that is obviously necessary in [BEGL96]. I do not yet have access to [Er97e] to check the statement there. The subtlety of this issue is unfortunate, given Aristotle's achievement!
Timing-wise, Aristotle took 6 hours and Lean took 1 minute.
-
Aristotle's solution is as follows. It is surprisingly easy.
Let $(a_n)$ be the sequence of powers of $d_i$ (sorted, with multiplicity). For example, if $d_1=2$ and $d_2=3$, then the sequences is: $1,1,2,3,4,8,9,16,27,\ldots$.
We want to show that every positive integer is a subsequence sum. This is equivalent to $a_{n+1} -1 \leq (a_1+\dots +a_n)$. The RHS is $\sum_{i=1}^k (d_i^{e_{i,n}}-1)/(d_i-1)$, where $e_{i,n}$ is the first power of $d_i$ that has not ocurred in the first $n$ terms. This is bounded below by $\min_i (d_i^{e_{i,n}}-1)$. However, $a_{n+1}=\min_i d_i^{e_{i,n}}$. Done.
Note, there is some ambiguity in the definition of $e_{i,n}$. In the example $d_1=2, d_2=3$, we can decide arbitrarily that $a_1$ is a power of $2$ and $a_2$ is a power of $3$, so $e_{2,1}=0$ but $e_{2,2}=1$.
-
For what it is worth, the Gemini and ChatGPT deep research tools did not turn up any significant new literature on this problem.
Gemini offered the simple observation that if 1 is omitted then the gcd condition becomes necessary, explained the significance of the $\sum_i \frac{1}{d_i-1} \geq 1$ condition (linking it to some parallel work on Cantor sets, particularly the "Newhouse gap lemma"), but turned up no new direct references for this problem.
ChatGPT used this very web page extensively as the main authoritative source, for instance citing the Aristotle proof, as well as the other papers cited on this page, as well as the page for the related problem [125]. As such, no new information was gleaned, but readers may find the AI-generated summary of the situation to be amusing.
-
G. Melfi in this paper has given the following related result:
A sequence $S = \{s_1, s_2,...\}$ of positive integers is a complete sequence, if $\Sigma (S) := \Sigma^\infty_{i=1} \epsilon_i s_i$, for $\epsilon_i \in \{0,1\}, \Sigma_{i=1}^\infty \epsilon_i < \infty$ contains all sufficiently large integers. Let $s \geq 1$ and $A$ be a (finite or infinite) set of integers greater than $1$. Let $Pow (A; s)$ be the nondecreasing sequence of positive integers of the form $a^k$ with $a \in A$ and $k \geq s$. for any $s \geq 1$, $Pow (A; s)$ is complete if and $\textbf{only if}$ $\Sigma_{a \in A} 1/(a-1) \geq 1$.
This $\textbf{only if}$ part of their conjecture has been disproved by Melfi in the above discussed paper.
P.S. [BEGL96] also asks the following:
What can we say about lower and upper asymptotic density of $Σ(Pow(A; s))$ when $A$ is finite and $\Sigma_{a \in A} \frac{1}{log a} > \frac{1}{log 2}$?
(According to page 13 of this paper).
All comments are the responsibility of the user. Comments appearing on this page are not verified for correctness. Please keep posts mathematical and on topic.