Erdős Problem #359
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
Start with a positive integer \(n\). Put \(a_1=n\), and having chosen the increasing sequence \(a_1<a_2<\cdots<a_k\), choose \(a_{k+1}\) to be the smallest integer that is not a sum of a nonempty consecutive block from the already chosen terms. Erdős Problem 359 asks how densely the resulting sequence occupies the positive integers. The especially studied case is \(n=1\).
For \(n=1\), the first question is whether the terms eventually become sparse enough that \(a_k/k\) tends to infinity. The second asks whether they remain far below every power strictly larger than linear: for each \(c>0\), does \(a_k/k^{1+c}\) tend to zero? Andrews proposed the sharper prediction
Here “consecutive” refers to consecutive positions in the sequence, not consecutive integers. Thus \(a_3\) is tested against \(a_1\), \(a_2\), and \(a_1+a_2\), while the order and the least-unrepresented rule matter at every later step. The general parameter \(n\) is part of the original problem, even though the two displayed limit questions concern \(n=1\).
A small example
For \(n=1\), exact integer arithmetic gives
The first nontrivial choices show the rule. From the prefix \(1,2\), the consecutive sums are \(1\), \(2\), and \(3\), so the least integer greater than \(2\) not represented is \(4\). From \(1,2,4\), the consecutive sums are \(1,2,3,4,6,7\); hence \(5\) is next. From \(1,2,4,5\), the values \(6\) and \(7\) are represented, but \(8\) is not, so the next term is \(8\).
The following finite checker was run with exact Python integers. It constructs every consecutive sum from the current prefix, searches upward from the previous term, and verifies the leastness condition through the fifteenth term:
A = [1]
for _ in range(14):
sums = {sum(A[i:j+1]) for i in range(len(A))
for j in range(i, len(A))}
x = A[-1] + 1
while x in sums:
x += 1
A.append(x)
print(A)
print(all(A[k] > A[k-1] and
all(y in {sum(A[i:j+1]) for i in range(k)
for j in range(i, k)}
for y in range(A[k-1] + 1, A[k])) and
A[k] not in {sum(A[i:j+1]) for i in range(k)
for j in range(i, k)}
for k in range(1, len(A))))
The observed output was the displayed list followed by True. This is a reproducible finite check of the recurrence for these fifteen terms. It does not establish that an infinite sequence exists for every parameter in the original wording, prove either limit, establish the asymptotic conjecture, or settle any density statement.
What is known
The readable primary source is Paul Erdős, “Problems and results on combinatorial number theory III,” Number Theory Day, Lecture Notes in Mathematics 626 (1977), pp. 43–72. On printed page 70, in the section on unconventional problems, Erdős describes the sequence beginning at \(1\) and says that Andrews conjectured its growth, while noting that he did not know even whether \(x_n/n\) tends to infinity. This is direct historical evidence that the lower-growth question was open in that source, not a modern proof-status certificate.
The current Erdős Problems entry, accessed 2026-10-13, still labels #359 open and says that it cannot be resolved by a finite computation. It identifies the sequence with OEIS A002048 and reports the initial terms above. It attributes the asymptotic prediction to George E. Andrews, “Mac Mahon’s Prime Numbers of Measurement,” American Mathematical Monthly 82 (1975), 922–923, and reports a result of Š. Porubský, “On MacMahon’s segmented numbers and related sequences,” Nieuw Arch. Wisk. (3) (1977), 403–408: for every \(epsilon>0\), infinitely many \(k\) satisfy
and, for the counting function \(A(x)\), the page reports \(\limsup A(x)/\pi(x)\ge 1/\log 2\). These are externally reported results here; the full Porubský paper was not available in the bounded source pass, so this article does not certify their proof details or translate them into a solved status.
GCL's current state
The frozen catalogue evidence is teorth/erdosproblems commit 536408716724a2402bdfa7c1d764bf83d64a8c89, data/problems.yaml, entry number: '359', blob 4e60263a80af6207aca494d2e1388e44fa372889. At that snapshot the catalogue state is open, last updated 2025-08-31; its formal-status field is unformalized, while statement-formalized metadata is yes. The protected GCL triage class is PROTECTED_READY_BACKLOG.
The pinned provider is google-deepmind/formal-conjectures commit 85f863718beeec7b58a3a1926ee92e3472bc2020, file FormalConjectures/ErdosProblems/359.lean, blob 62635546c38f181610242b83e1e5d5ca86b5d64a. It defines IsGoodFor on \(\mathbb N\to\mathbb N\), uses zero-based indexing, requires strict monotonicity and \(A(0)=1\), and formalizes the two limits plus finite values and the Andrews asymptotic as separate theorem statements. Every theorem body is by sorry; presence of these statements is not a verified Lean proof or a claim of semantic equivalence with the source.
No prior RESULT/1 exists in issue #1629 or in the EC-BULK-003 readback for this assignment. The original SOURCE RESULT/1 citation is authenticated original RESULT/1.
What remains
The smallest useful next step is a source-and-semantics bridge, not an attempt to infer a global theorem from the first terms. It should fix whether the original problem permits only positive integers, make “sum of consecutive earlier terms” explicitly nonempty, align one-based source indices with the Lean zero-based encoding, and compare the general parameter \(n\) source question with the pinned file’s \(n=1\) theorem statements. The finite checker can then serve as a regression certificate for a chosen prefix.
A later research task could separately audit Andrews’s asymptotic and Porubský’s bounds against their primary texts, recording exact theorem or page locations and hypotheses. Its acceptance test should be a line-by-line statement match plus a reproducible finite test; its stopping rule should be an unresolved source or quantifier mismatch, not a guessed status. Nothing in the finite computation or in the sorry-based formal file resolves the infinite problem.
Sources and claim boundaries
The original assignment and its source packet are MATH-PROGRAMME issue #1629. The live statement and dated status are Erdős Problems #359, with its LaTeX source and OEIS A002048. The directly read primary source is Erdős’s 1977 survey PDF, especially printed p. 70. Andrews’s primary bibliographic record is the 1975 American Mathematical Monthly article; its publisher page exposes the citation but the full text was not available in this pass. The live entry supplies the Porubský citation and MR 485763, but the primary article itself was not read.
The frozen catalogue and formal-file commit and blob identities above are the reproducibility boundary. The live webpage is mutable and is cited with its access date, not treated as an immutable replacement for the packet. This is a documentary source audit, not mathematical certification, Lean replay, publication approval, or a declaration that the catalogue status has been changed. V2 ledger evidence alone decides accepted coverage.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1629 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: PROTECTED_READY_BACKLOG.
- Formal-statement coverage: A provider statement was included in the pinned snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.