Erdős Problem #341

Erdős Problem 341: a greedy sum-avoiding sequence

Statement and scope

From a finite positive seed, repeatedly append the least integer larger than the current maximum which is not a sum of two already present elements, allowing equal summands. Must the successive differences eventually be periodic?

We prove a finite certification criterion, settle all seeds $\{1,\ldots,k\}$, and give an exact finite certificate for the stated seed $\{1,4,9,16,25\}$. The assertion for every seed is unresolved here. Source: https://www.erdosproblems.com/341. This extends the earlier GPT-5.2 examples; the particular periodicity is known experimental context, and no new general theorem is claimed.

All initial-interval seeds

For seed $\{1,\ldots,k\}$, the completed sequence is \[ \{1,\ldots,k\}\ \cup\ \{2k+1+j(k+1):j\ge0\}. \tag{1} \] Initially every integer from $k+1$ through $2k$ is a sum of two seed elements, so $2k+1$ is next. Suppose the current last tail element is $b$. The next $k$ integers $b+1,\ldots,b+k$ are forbidden by adding the seed elements. The following number $b+k+1$ has residue $k\bmod(k+1)$. A seed plus a tail element has any residue except $k$; two tail elements have residue $k-1$. Two seed elements have sum at most $2k$. Thus $b+k+1$ is admissible. Induction proves $1$, with eventual constant gap $k+1$.

A finite certificate that implies infinite periodicity

Fix $T$ above the seed maximum, a positive integer $p$, a finite $F\subset[1,T-1]$, and $R\subset\mathbb Z/p\mathbb Z$. Consider \[ E=F\cup\{n\ge T:n\bmod p\in R\}. \] Put $Q=(R+R)\cup(F+R)\bmod p$ and $N_0=2(T+p)$. If \[ Q=(\mathbb Z/p\mathbb Z)\setminus R \tag{2} \] and the actual greedy sequence agrees with $E$ below $N_0$, then it agrees forever.

To prove this, for every $n\ge N_0$ we have $n\in E+E$ exactly when its residue lies in $Q$. Two finite members sum to less than $2T$. A tail residue has a positive representative in $[T,T+p-1]$; thus every residue of $R+R$ has a two-tail representation of size below $N_0$, and adding multiples of $p$ to one tail summand represents every larger integer of that residue. The same argument works for $F+R$. This proves the equivalence.

Now induct on $n\ge N_0$. Both positive summands in a representation of $n$ are smaller than $n$, so previous agreement determines its admissibility exactly. Equation $2$ says that the greedy rule includes precisely the residues in $R$. This completes the induction. The resulting differences have a repeating word of $|R|$ gaps, whose sum is $p$.

An exact certificate for the five-square seed

For $\{1,4,9,16,25\}$, take \[ T=440,\qquad p=1176,\qquad N_0=3232. \] Let $F$ be the generated terms below $440$, and let $R$ be the residues of the generated terms in $[440,1616)$. Exact finite arithmetic gives $|F|=86$, $|R|=224$, and verifies both hypotheses of the criterion. The following self-contained code specifies and checks the certificate; it generates only the finite prefix needed for the proof.

T, p = 440, 1176
N0 = 2*(T+p)
chosen = {1, 4, 9, 16, 25}
sums = {a+b for a in chosen for b in chosen}
for n in range(26, N0):
    if n not in sums:
        sums.update(n+a for a in chosen)
        sums.add(2*n)
        chosen.add(n)
F = {n for n in chosen if n < T}
R = {n % p for n in chosen if T <= n < T+p}
Q = {(r+s) % p for r in R for s in R}
Q |= {(f+r) % p for f in F for r in R}
assert len(F) == 86 and len(R) == 224
assert Q == set(range(p)) - R
assert chosen == F | {n for n in range(T, N0)
                       if n % p in R}

These checks were run successfully. By the proved criterion, membership repeats modulo $1176$ from $440$ onward. Thus $224$ is a period of the eventual gap word, and the sequence has density $224/1176=4/21$. A finite repetition alone would not prove this conclusion; equation $2$ is the additional invariant.

Remaining gap

The certificate is sufficient once a periodic model is supplied. Nothing above ensures that every seed eventually supplies one, which is precisely the general problem.

COMPLETION ESTIMATE

COMPLETION: 60%

Erdős problem #341

1) FORMAL RESTATEMENT. Start from a finite set $A\subseteq\mathbb{N}$. Define a sequence $a_1<a_2<\cdots$ by taking $\{a_1,\dots,a_n\}$ to be the set of elements constructed so far (initially the given $A$), and then defining $a_{n+1}$ to be the smallest integer $>a_n$ which is not of the form $a_i+a_j$ with $i,j\le n$ (repetitions allowed). Equivalently, we repeatedly adjoin the smallest integer larger than the current maximum that does not lie in the sumset of the current set with itself.

The question: are the successive differences $a_{n+1}-a_n$ eventually periodic for every starting set $A$?

2) QUICK LITERATURE/CONTEXT CHECK. The statement reports that for $A=\{1,4,9,16,25\}$ one needs thousands of terms before periodicity appears. No other results are assumed.

3) ATTACK PLAN.

• Work out small initial sets explicitly and prove eventual periodicity in those cases.
• Use these examples to identify simple sufficient conditions for immediate periodicity.
• Compute the first few terms for the given example $\{1,4,9,16,25\}$ as a sanity check.

4) WORK.

Lemma 341.1 (starting from $\{1\}$ gives all odd numbers). If the initial set is $A=\{1\}$, then the greedy sequence is \[ a_n = 2n-1\quad(n\ge 1), \] so the difference sequence is identically $2$ (hence periodic).

Proof. We prove by induction that after $n$ steps the set is exactly $\{1,3,5,\dots,2n-1\}$. This is true for $n=1$. Assume it holds for some $n\ge 1$. Then every sum of two elements of the set is even, so no odd integer $>2n-1$ is representable as such a sum. In particular, the smallest integer $>2n-1$ not representable as a sum is the next odd number $2n+1$ (since the even number $2n$ is representable as $1+(2n-1)$). Thus $a_{n+1}=2n+1$ and the claim follows. $\square$

Lemma 341.2 (starting from $\{1,2\}$ gives an arithmetic progression). If the initial set is $A=\{1,2\}$, then the greedy sequence is \[ a_1=1,\ a_2=2,\ \text{and}\ a_n = 3n-4\ \text{for all }n\ge 2. \] Equivalently, from $a_2$ onward the differences are constantly $3$.

Proof. We prove by induction on $m\ge 0$ that after constructing up to the value $b_m:=2+3m$, the set equals \[ S_m:=\{1\}\cup\{2,5,8,\dots,2+3m\}. \] The base case $m=0$ is the initial set $\{1,2\}$. Assume the set is $S_m$ with maximum element $b_m=2+3m$. Consider the next integers.

First, $b_m+1=3(m+1)$ is representable as $1+b_m$. Second, $b_m+2=3m+4$ is representable as $2+b_m$. So both $b_m+1$ and $b_m+2$ are forbidden. Now $b_m+3=2+3(m+1)$ is congruent to $2\pmod 3$. Every sum of two elements of $S_m$ is congruent to $0$ or $1$ modulo $3$:

• sums of two elements from $\{2+3j\}$ are $\equiv 1\pmod 3$,
• sums of $1$ with an element $2+3j$ are $\equiv 0\pmod 3$,
• and $1+1=2$ is the only sum $\equiv 2\pmod 3$.

In particular, for $m\ge 0$ we have $b_m+3\ge 5$, so $b_m+3$ cannot equal $1+1$, hence it is not representable as a sum of two elements of $S_m$. Therefore the greedy rule selects $b_m+3$ as the next element. Thus $S_{m+1}$ is obtained, completing the induction. $\square$

FAST REALITY CHECK (computed examples). By brute force, the first $20$ terms for several seeds are:

• $A=\{1\}$: $1,3,5,7,\dots,39$ (all odds), differences all $2$.
• $A=\{1,2\}$: $1,2,5,8,11,\dots,56$, differences $1,3,3,3,\dots$.
• $A=\{1,4,9,16,25\}$: $1,4,9,16,25,27,30,33,35,38,40,45,48,53,59,74,77,79,82,87$, with nonperiodic-looking early differences.

5) VERIFICATION. Both Lemmas 341.1 and 341.2 are proved by explicit induction using modular/parity obstructions that are specific to the constructed sets.

6) FINAL.

UNRESOLVED

(i) Strongest fully proved partial result obtained here. We proved eventual periodicity (indeed immediate periodicity) for two nontrivial starting sets: $\{1\}$ yields all odd numbers (Lemma 341.1) and $\{1,2\}$ yields an eventual arithmetic progression with step $3$ (Lemma 341.2).

(ii) Exact first gap. We do not have a proof that the difference sequence is eventually periodic for every starting finite set $A$. The first gap is understanding how the set of forbidden sums evolves and whether it forces eventual periodic structure.

(iii) Top 3 next moves (concrete targets).

1. Prove a general "modular trapping" lemma: identify conditions under which the greedy set eventually becomes a union of residue classes modulo some $m$, which would force periodic differences.
2. For the specific seed $\{1,4,9,16,25\}$, compute much longer prefixes and attempt to detect a candidate period and preperiod, then attempt to prove it by verifying closure properties of the forbidden-sum set modulo that period.
3. Establish monotonicity/regularity properties of the forbidden-sum set (e.g. eventual interval coverage in each residue class) that imply periodicity of the complement.

(iv) Minimal counterexample structure. A counterexample would be a finite seed $A$ for which the greedy sequence's difference word never becomes periodic. Any such seed would have to avoid falling into a finite-state modular pattern; one expects it would force infinitely many "new" local configurations of representability by sums, preventing eventual repetition.