Growth of the greedy sequence whose terms are the least new sum of $\ge 2$ consecutive earlier terms (Erdős #423)
Statement
Define a sequence by $a_1=1$, $a_2=2$, and for $k\ge 3$ let $a_k$ be the least integer $>a_{k-1}$ that can be written as a sum of at least two consecutive terms $a_i+a_{i+1}+\cdots+a_j$ (with $i<j$) of the already-constructed sequence. The sequence begins $1,2,3,5,6,8,10,11,\ldots$. Determine the asymptotic behaviour of $a_n$ — in particular, is $a_n=n+o(n)$?
Acceptance. FULLY RESOLVES: determine the true asymptotics of $a_n$ with a complete proof — e.g. a proof that $a_n=n+o(n)$ (or a proof of the correct order if it differs), machine-checkable or fully written. ADVANCES (each independently checkable): (a) improve the upper-bound exponent strictly below the best stated in the background (currently $a_n\ll n^{1.6659+o(1)}$), with proof or via a stated improved convex-set difference bound; (b) improve the lower bound strictly beyond $a_n=n+\Omega(\log\log n)$, with proof; (c) extend the verified computation of the sequence to a new record $N$ with reproducible code, reporting the observed growth of $a_n-n$. Deliver the proof, or the generator code plus the attained $N$ and the fitted growth data.
Background
Asked by Hofstadter; Erdős [Er77c, p.71] notes he was inspired by a related question of Ulam, and it also appears in Erdős–Graham [ErGr80, p.83]. It is A005243 in the OEIS. Listed as open on erdosproblems.com/423 (fetched 2026-07-13, status 'open', tagged 'number theory'). Frontier: Bolan and (independently) Tang [Ta26] proved that infinitely many integers are missing — in fact $a_n-n$ is nondecreasing and unbounded. Tang [Ta26] further showed that $a_n\ll n^{\frac{1}{c-1}+o(1)}$ holds for any convex-set difference exponent $c$ — i.e. any $c$ satisfying $\lvert A-A\rvert\ge\lvert A\rvert^{c-o(1)}$ for every convex $A$; the current convex-set difference bound of Cushman [Cu25] gives $a_n\ll n^{688/413+o(1)}\le n^{1.6659+o(1)}$. The Erdős–Hegyvári conjecture that one may take $c=2$ for convex sets would yield $a_n\le n^{1+o(1)}$, and it is believed the truth is $a_n=n+o(n)$. Tang also proved an improved lower bound $a_n=n+\Omega(\log\log n)$. The attacker's tool: generate the sequence to a large record $N$ with efficient consecutive-sum bookkeeping to test $a_n=n+o(n)$ and to measure the growth of $a_n-n$; on the theory side, sharpen the upper exponent via convex-set / $\lvert A-A\rvert$ estimates or push the $a_n-n$ lower bound.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #423 (T. F. Bloom) | website |
| REF-02 | OEIS A005243 — least integer that is a sum of >=2 consecutive earlier terms (Ulam-type) | website |
| REF-03 | Bolan, notes proving infinitely many integers are missed by the Hofstadter–Ulam sequence | paper |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.