For any d≥ 1 and k≥ 0 let P(d,k) be the set of integers which are the sum of distinct powers d^i with i≥ k. Let 3≤ d_1<d_2<… <d_r be integers such that ∑_1≤ i≤ rfrac1d_r-1≥ 1. Can all sufficiently large integers be written as a sum of the shape ∑_i c_ia_i where c_i∈ 0,1 and a_i∈ P(d_i,0)? If we further have gcd(d_1,…,d_r)=1 then, for any k≥ 1, can all sufficiently large integers be written as a sum of the shape ∑_i c_ia_i where c_i∈ 0,1 and a_i∈ P(d_i,k)?

Erdős Problem #124 — 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$ .

About 30 years old · traced to 1996

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)$ ?

References

Primary source

ULAM AI, UnsolvedMath dataset, Erdős Problems set, revision b9437975f3c873f635a13c48f8b022f5ba80898a; CC BY 4.0.

Additional references

UnsolvedMath, Erdős Problems set, ULAM AI, licensed CC BY 4.0.

base-representations number-theory

InErdős Problems

Posted 2 months ago · edited 3 weeks ago

Progress summary

Refreshed 1 month ago

Claimed progress

The unrestricted question has been formally solved, but the version forbidding low powers remains open.

Erdős asked the first question in [Er97] and [Er97e]. Burr, Erdős, Graham, and Li conjectured the second question in [BEGL96], with the coprimality condition and the restriction to positive powers.

Known results

Burr, Erdős, Graham, and Li, 1996: proved the second question for the bases $\{3,4,7\}$ .
Pomerance: observed that $\sum_i 1/(d_i-1)\geq 1$ is necessary for finite base sets.
Melfi, 2004: constructed infinite base sets with $\sum_i 1/(d_i-1)<\epsilon$ still having the unrestricted representation property.

Formal solution of the first question

Boris Alexeev, using Aristotle, supplied a Lean-formalized positive proof of the unrestricted question via the complete-sequence inequality. The formal-conjectures record marks it “research solved,” while the positive-power question remains “research open.”

Current status (as of December 2025): the unrestricted question is formally resolved, while the coprime positive-power question remains open.

AristotleHarmonicpartial progressevidence

Sources

No solutions have been posted yet.