Eventual periodicity of the gaps of Dickson's greedy sum-avoiding sequence (Erdős #341)
Statement
Let $A=\{a_1<\cdots<a_k\}$ be a finite set of positive integers. Extend it to an infinite increasing sequence $\overline{A}=\{a_1<a_2<\cdots\}$ by the greedy rule: for each $n\geq k$, let $a_{n+1}$ be the least integer exceeding $a_n$ that is not of the form $a_i+a_j$ for any $i,j\leq n$ (the indices $i,j$ need not be distinct). Is the sequence of consecutive differences $a_{m+1}-a_m$ eventually periodic, for every finite starting set $A$?
Acceptance. FULLY RESOLVES: either a proof that for every finite starting set the difference sequence $a_{m+1}-a_m$ is eventually periodic, or an explicit finite starting set together with a proof that its difference sequence is NOT eventually periodic. Because the problem is OPEN (no finite computation can settle it), a long non-repeating computation alone does not suffice — non-periodicity must be proved. ADVANCES (each independently checkable): (a) rigorously establish eventual periodicity for a specific starting set or an explicit infinite family — e.g. prove that $\{1,4,9,16,25\}$ has eventually periodic differences by exhibiting the pre-period and period plus a machine-checkable certificate that the set of representable sums is eventually periodic; or (b) compute, with reproducible code, the sequence for named starting sets far beyond the currently published extent, reporting the observed pre-period and period or a certified record length over which the gaps do not repeat. Deliver a proof or code plus the periodicity certificate.
Background
An old problem of Dickson, recorded by Erdős–Graham [ErGr80, p.53]; listed as open on erdosproblems.com/341 (fetched 2026-07-13, status 'open', tagged 'number theory'). The phenomenon is subtle even experimentally: a starting set as small as $\{1,4,9,16,25\}$ requires thousands of terms before its differences settle into an apparent period. The problem is discussed as Problem 7 on Ben Green's open-problems list. It sits alongside the other greedy sum-defined Erdős sequences — the Ulam numbers of Erdős #342 (erdosproblems.com/342) and the consecutive-sum sequence of Erdős #359 (erdosproblems.com/359) — which raise the same eventual-periodicity and density questions. Erdős attached no prize; no OEIS entry is listed. The attacker's tool: generate the greedy sequence to very large length for many starting sets (efficiently maintaining the set of representable sums $a_i+a_j$), detect eventual periodicity, and — once the representable-sum set becomes eventually periodic — certify the period rigorously; alternatively, search for a starting set whose gaps resist periodicity to a record length.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #341 (T. F. Bloom) | website |
| REF-02 | B. J. Green, Open problems (Problem 7) | paper |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.