Erdős Problem #423
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: number theory.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
The question in plain language
The Hofstadter consecutive-sum sequence starts with \(a_1=1\), \(a_2=2\). For each \(k\geq3\), its next term is the smallest integer strictly greater than the preceding term that can be expressed as a sum of at least two consecutive earlier terms of the selected sequence. This is a greedy construction: earlier selected numbers determine which larger numbers may be chosen.
Erdős Problem 423 asks how the sequence grows as \(k\) tends to infinity. Does it eventually select almost every positive integer? How many integers are never selected? How large is \(a_k-k\)? These are distinct questions: even infinitely many omitted integers could form a set of density zero.
The word consecutive refers to adjacent indices in the selected sequence, not necessarily adjacent positive integers. A permitted block must have at least two members, and only already selected terms are available at each step.
A small example
Start with \(1,2\). Their sum gives \(a_3=3\). Among block sums of \(1,2,3\), the smallest one above \(3\) is \(2+3=5\), so \(a_4=5\). The integer \(4\) is skipped. The next entries include \(6=1+2+3\), \(8=3+5\), \(10=2+3+5\), and \(11=5+6\). Direct exact-integer enumeration gives
The result agrees with OEIS A005243. Some small numbers absent from the displayed prefix are \(4,7,9,12,13,15,20\). An observed finite omission cannot by itself prove that infinitely many omissions occur.
There is an exact counting identity. Put \(b_k=a_k-k\). The first \(k\) selected terms are precisely the \(k\) selected positive integers not exceeding \(a_k\). Hence
The excess \(b_k\) therefore counts the omitted integers up to \(a_k\). Since \(a_{k+1}\geq a_k+1\), we have \(b_{k+1}\geq b_k\). This proves monotonicity but not unboundedness. A nondecreasing integer sequence could become constant.
What is known
Erdős recorded Hofstadter's question in Problems and results on combinatorial number theory, III (1977), printed p. 71, and again with Graham in Old and New Problems and Results in Combinatorial Number Theory (1980), printed p. 83 of the scan. Hofstadter was inspired by a related question of Ulam.
Quanyu Tang's 2026 preprint, The Hofstadter consecutive-sum sequence omits infinitely many positive integers, makes a substantial advance. Theorem 1.3 proves that \(b_k=a_k-k\) is nondecreasing and unbounded; consequently infinitely many positive integers are never selected. The maintained Erdős Problems #423 entry credits Matthew Bolan with an independent proof of this qualitative assertion.
Tang's Theorem 1.4 gives a quantitative lower bound of order \(\log\log k\) for the excess, and Theorem 1.5 provides a polynomial upper bound on \(a_k\). The maintained problem page reports a stronger upper bound obtained using later estimates for difference sets of finite convex sets:
This is not an asymptotic equality and not proof that \(a_k/k\) tends to one. The maintained status remains OPEN for the original question of precise asymptotic growth. Infinitely many omissions have been proved; complete asymptotics have not been settled.
GCL's current state
The original GCL issue #1693 pins the teorth catalogue at commit 536408716724a2402bdfa7c1d764bf83d64a8c89, data/problems.yaml blob 4e60263a80af6207aca494d2e1388e44fa372889. Its frozen status is open in August 2025, and the current maintained status remains open for the broader question despite Tang's 2026 partial resolution.
The source issue explicitly identifies no formal statement file for Problem 423 in the admitted FormalConjectures revision 85f863718beeec7b58a3a1926ee92e3472bc2020. It would be incorrect to silently import a newer upstream formalization or to treat an absent file as a completed Lean proof. No formal replay or proof certification is claimed.
The authenticated original-issue source return is RESULT/1 comment #6157191320. This binds the exposition to the correct issue, but editorial acceptance remains a separate V2-ledger decision.
What remains
A bounded successor can calculate the first 100 selected terms in two independent ways. One algorithm enumerates all sums of at least two consecutive previously selected terms before each greedy choice. Another maintains an incrementally updated set of eligible block sums. Both should reproduce the same terms, and the identity \(b_k=a_k-k\) should match a direct count of omitted positive integers to \(a_k\) at every stage.
A source audit should transcribe the precise hypotheses and conclusions of Tang's Theorems 1.3–1.5, and identify the convex-set difference estimate behind the maintained improved exponent. The successor is accepted if both integer algorithms agree, each selected number has a valid block witness, and the published lower and upper bounds remain distinct from the unsolved exact asymptotics. A mismatched greedy term, a false block sum, or a claim that infinitely many omissions means positive-density omissions falsifies the proposed result. Stop at this finite fixture and source-concordance boundary.
Sources and claim boundaries
Original sources: Erdős (1977), p. 71, and Erdős–Graham (1980), p. 83. Primary research: Quanyu Tang, arXiv:2603.09939, Theorems 1.3–1.5. Maintained current status: Erdős Problem #423. Numerical checksum: OEIS A005243. Source custody: original GCL issue #1693 and authenticated source audit.
The finite block sums and excess-count identity are independently reproducible. Tang's theorem is an external mathematical result, not a newly proved GCL theorem. Neither exact asymptotics, Lean certification, nor protected editorial admission is asserted.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1693 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: FORMAL_SOURCE_REFRESH_REQUIRED.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.