# P3038: Erdős Problem 124: Sums of Distinct Powers with Nonzero Exponent Shift

- ID: `P3038`
- Reference: `erdos-problem-124`
- Page: https://theoremdb.org/statements/P3038
- Record maturity: Reviewed problem with recorded work

## Problem

Erdős Problem 124: Let $k$ be a nonzero integer, and let $D$ be a finite set of integers, each at least $3$, such that
\[\sum_{d \in D} \frac{1}{d-1} \geq 1\]
and $\gcd(D) = 1$. For each $d \in D$ and each integer $k \geq 0$, let $S(d,k)$ denote the set of natural numbers that can be written as
\[\sum_{i \in s} d^i\]
for some finite set $s$ of integers with $i \geq k$ for all $i \in s$. Does every sufficiently large natural number belong to the set
\[\sum_{d \in D} S(d,k),\]
that is, can it be expressed as $\sum_{d \in D} x_d$ where $x_d \in S(d,k)$ for each $d \in D$?

### Context

This problem is a variant of a classical question about representing integers as sums of numbers with restricted digits in multiple bases. The case $k = 0$ was solved affirmatively by Boris Alexeev. The case with $k \neq 0$ and the additional coprimality condition was conjectured by Burr, Erdős, Graham, and Li.

### Problem setup

- **Definition (For integers $d \geq 2$ and $k \geq 0$, the set $S(d,k)$ of sums of distinct powers (with exponent at least $k$) consists of all natural numbers of the form $\sum_{i \in s} d^i$ where $s$).** For integers $d \geq 2$ and $k \geq 0$, the set $S(d,k)$ of sums of distinct powers (with exponent at least $k$) consists of all natural numbers of the form $\sum_{i \in s} d^i$ where $s$ is a finite set of integers satisfying $i \geq k$ for all $i \in s$. Equivalently, these are numbers whose base-$d$ representation contains only digits $0$ or $1$, with all nonzero digits occurring at positions corresponding to exponents at least $k$.
- **Definition (For a finite set $D$ of natural numbers, $\gcd(D)$).** For a finite set $D$ of natural numbers, $\gcd(D)$ denotes the greatest common divisor of all elements of $D$.
- **Definition (The notation $\sum_{d \in D} S(d,k)$).** The notation $\sum_{d \in D} S(d,k)$ denotes the Minkowski sum of the sets $S(d,k)$ over all $d \in D$, consisting of all sums $\sum_{d \in D} x_d$ where $x_d \in S(d,k)$ for each $d \in D$.
- **Definition (The phrase 'every sufficiently large natural number').** The phrase 'every sufficiently large natural number' means that there exists some natural number $N$ such that the property holds for all natural numbers $n \geq N$.
- **Remark.** This problem is a variant of a classical question about representing integers as sums of numbers with restricted digits in multiple bases. The case $k = 0$ was solved affirmatively by Boris Alexeev. The case with $k \neq 0$ and the additional coprimality condition was conjectured by Burr, Erdős, Graham, and Li.

### What counts as a solution

- Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 124: Let $k$ be a nonzero integer, and let $D$ be a finite set of integers, each at least $3$, such that
\[\sum_{d \in D} \frac{1}{d-1} \geq 1\]
and $\gcd(D) = 1$. For each $d \in D$ and each integer $k \geq 0$, let $S(d,k)$ denote the set of natural numbers that can be written as
\[\sum_{i \in s} d^i\]
for some finite set $s$ of integers with $i \geq k$ for all $i \in s$. Does every sufficiently large natural number belong to the set
\[\sum_{d \in D} S(d,k),\]
that is, can it be expressed as $\sum_{d \in D} x_d$ where $x_d \in S(d,k)$ for each $d \in D$?

## Status

OPEN as of 2026-07-31. The maintained Erdős Problems database at commit 8138974387d9030542daabe67faaa33eff9356f8 lists Problem 124 as open. The unresolved remainder is the full displayed statement. Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 124: Let $k$ be a nonzero integer, and let $D$ be a finite set of integers, each at least $3$, such that
\[\sum_{d \in D} \frac{1}{d-1} \geq 1\]
and $\gcd(D) = 1$. For each $d \in D$ and each integer $k \geq 0$, let $S(d,k)$ denote the set of natural numbers that can be written as
\[\sum_{i \in s} d^i\]
for some finite set $s$ of integers with $i \geq k$ for all $i \in s$. Does every sufficiently large natural number belong to the set
\[\sum_{d \in D} S(d,k),\]
that is, can it be expressed as $\sum_{d \in D} x_d$ where $x_d \in S(d,k)$ for each $d \in D$? [1](#reference-1)

## Work

### Evidence for the current status

**Claim 1 (Current status and unresolved remainder).** OPEN as of 2026-07-31. The maintained Erdős Problems database at commit 8138974387d9030542daabe67faaa33eff9356f8 lists Problem 124 as open. The unresolved remainder is the full displayed statement. Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 124: Let $k$ be a nonzero integer, and let $D$ be a finite set of integers, each at least $3$, such that
\[\sum_{d \in D} \frac{1}{d-1} \geq 1\]
and $\gcd(D) = 1$. For each $d \in D$ and each integer $k \geq 0$, let $S(d,k)$ denote the set of natural numbers that can be written as
\[\sum_{i \in s} d^i\]
for some finite set $s$ of integers with $i \geq k$ for all $i \in s$. Does every sufficiently large natural number belong to the set
\[\sum_{d \in D} S(d,k),\]
that is, can it be expressed as $\sum_{d \in D} x_d$ where $x_d \in S(d,k)$ for each $d \in D$?

OPEN as of 2026-07-31. The maintained Erdős Problems database at commit 8138974387d9030542daabe67faaa33eff9356f8 lists Problem 124 as open. The unresolved remainder is the full displayed statement.

A complete resolution must satisfy this condition: Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 124: Let $k$ be a nonzero integer, and let $D$ be a finite set of integers, each at least $3$, such that
\[\sum_{d \in D} \frac{1}{d-1} \geq 1\]
and $\gcd(D) = 1$. For each $d \in D$ and each integer $k \geq 0$, let $S(d,k)$ denote the set of natural numbers that can be written as
\[\sum_{i \in s} d^i\]
for some finite set $s$ of integers with $i \geq k$ for all $i \in s$. Does every sufficiently large natural number belong to the set
\[\sum_{d \in D} S(d,k),\]
that is, can it be expressed as $\sum_{d \in D} x_d$ where $x_d \in S(d,k)$ for each $d \in D$?

### Background and intake notes

- Original intake status: OPEN as of 2026-07-31. The maintained Erdős Problems database at commit 8138974387d9030542daabe67faaa33eff9356f8 lists Problem 124 as open. The unresolved remainder is the full displayed statement.
- The maintained database entry for Erdős Problem 124 was open at commit 8138974387d9030542daabe67faaa33eff9356f8.
- The pinned Formal Conjectures declaration was matched by problem number and source locator.
- The controlled TheoremDB source corpus was checked for an already published record with the same slug.

### Open directions

- **Route 1** (reported): Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 124: Let $k$ be a nonzero integer, and let $D$ be a finite set of integers, each at least $3$, such that \[\sum_{d \in D} \frac{1}{d-1} \geq 1\] and $\gcd(D) = 1$. For each $d \in D$ and each integer $k \geq 0$, let $S(d,k)$ denote the set of natural numbers that can be written as \[\sum_{i \in s} d^i\] for some finite set $s$ of integers with $i \geq k$ for all $i \in s$. Does every sufficiently large natural number belong to the set \[\sum_{d \in D} S(d,k),\] that is, can it be expressed as $\sum_{d \in D} x_d$ where $x_d \in S(d,k)$ for each $d \in D$? [1](#reference-1)

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `erdos-problem-124`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>Erdős Problems database, Problem 124, maintained status record. Erdős Problems record 124, checked 2026-08-01. Problem 124; status field and linked bibliography https://www.erdosproblems.com/124
   - Also cited at Problem 124; status snapshot 8138974387d9030542daabe67faaa33eff9356f8
   - Also cited at See dataset.references[0] for the exact external source and locator.
   - Also cited at Editorial research route recorded 2026-07-31
   - reference_database; reference source; commit 8138974387d9030542daabe67faaa33eff9356f8; checked 2026-07-31
   - Source use: original_summary
   - Records the current open status and links the literature attached to this exact numbered problem.
   - Source used to formulate or check the problem record.
   - Source used to assess the problem's recorded status.
   - For Erdős Problem 124: Sums of Distinct Powers with Nonzero Exponent Shift: Records the current open status and links the literature attached to this exact numbered problem.
   - Source named by the research packet.
2. <a id="reference-2"></a>Erdős problem database, data/problems.yaml, commit 8138974387d9030542daabe67faaa33eff9356f8. Problem 124 entry in data/problems.yaml https://github.com/teorth/erdosproblems/blob/8138974387d9030542daabe67faaa33eff9356f8/data/problems.yaml
   - reference_database; reference source; commit 8138974387d9030542daabe67faaa33eff9356f8; checked 2026-07-31
   - Source use: original_summary
   - Pins the maintained database snapshot used for this release's dated status decision.
   - Source used to assess the problem's recorded status.
   - For Erdős Problem 124: Sums of Distinct Powers with Nonzero Exponent Shift: Pins the maintained database snapshot used for this release's dated status decision.
3. <a id="reference-3"></a>Google DeepMind, Formal Conjectures, formal statement for Erdős Problem 124. GitHub commit bb1c69dab14ad895ac1ccdb7b0c0e0a67c8eb3e1. FormalConjectures/ErdosProblems/124.lean:L58; lemma erdos124.ne_zero; commit bb1c69dab14ad895ac1ccdb7b0c0e0a67c8eb3e1 https://github.com/google-deepmind/formal-conjectures/blob/bb1c69dab14ad895ac1ccdb7b0c0e0a67c8eb3e1/FormalConjectures/ErdosProblems/124.lean#L58
   - reference_database; primary source; commit bb1c69dab14ad895ac1ccdb7b0c0e0a67c8eb3e1; checked 2026-07-31
   - Source use: original_summary
   - Supplies the pinned formal declaration whose human-readable editorial statement is published here.
   - Source used to assess the problem's recorded status.
   - For Erdős Problem 124: Sums of Distinct Powers with Nonzero Exponent Shift: Supplies the pinned formal declaration whose human-readable editorial statement is published here.