Erdős Problem #422
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 \(Q\) sequence is a self-referential recurrence. Its first two terms are \(Q(1)=Q(2)=1\). For every later index the rule is
The previously calculated values determine how far backwards to look before adding two terms. Erdős Problem 422 asks whether infinitely many positive integers are absent from the sequence's range, and more broadly how the sequence grows. This is different from Problem 423, which concerns a greedy sequence of consecutive sums.
There is an unresolved preliminary point. For the recursion to be valid, both indices \(n-Q(n-1)\) and \(n-Q(n-2)\) must be positive and strictly smaller than \(n\). Finite computations verify that condition for the indices they visit, but do not establish that the recurrence can be continued for all positive integers. The maintained source explicitly notes this issue.
A small example
Successively applying the recurrence yields
For example \(Q(3)=Q(2)+Q(2)=2\), and \(Q(4)=Q(2)+Q(3)=3\). At index \(16\), \(Q(16)=9\) even though \(Q(15)=10\). The sequence is therefore not monotone: an integer absent from a short prefix might still appear much later.
I independently calculated the first 500 terms with exact integer arithmetic, explicitly checking that each recursive argument lay between \(1\) and \(n-1\) before using it. No invalid argument was found in that finite range. Of the candidate values \(1\) through \(50\), the values
did not occur among those first 500 terms. This is a bounded nonobservation, not a proof that even one of them is omitted forever. A later term could attain a previously unseen value, and finite testing cannot prove infinitely many globally missing values.
To reproduce the test, initialize an array of positive integers with \(Q(1)=Q(2)=1\). For each \(n\geq3\), first calculate \(a=n-Q(n-1)\) and \(b=n-Q(n-2)\). Reject the step if \(a\) or \(b\) is not an earlier positive index; otherwise append \(Q(a)+Q(b)\). Store the two input indices along with each term as an auditable computational receipt.
What is known
The historical question occurs in P. Erdős and R. L. Graham, Old and New Problems and Results in Combinatorial Number Theory (1980), printed page 83 of the scanned monograph. It credits Douglas Hofstadter, notes the irregularity of the sequence and asks about omitted values and long-term growth.
The maintained Erdős Problems #422 page still classifies this question as OPEN. It identifies the standard sequence as OEIS A005185 and explicitly says that well-definedness for all \(n\) is not known. An OEIS numerical prefix is a useful cross-check but cannot certify an infinite theorem.
Klaus Pinn, Order and chaos in Hofstadter's Q(n) sequence, subsequently published in Complexity 4(3) (1999), 41–46, studied empirical scaling, generations and the irregular fluctuations. The reported numerical behavior is relevant background, but the article's finite and statistical observations do not amount to a general proof of recurrence totality or infinitely many omitted integers.
The distinction between an empirical pattern and a theorem is especially important here. If one could prove that all recursive arguments are earlier positive indices, global well-definedness would follow by induction. Yet the bound sufficient for this step is precisely what remains unproved uniformly. Computation across a huge interval does not substitute for an invariant holding for every index.
GCL's current state
The original GCL assignment #1692 pins the teorth catalogue at commit 536408716724a2402bdfa7c1d764bf83d64a8c89, file data/problems.yaml, blob 4e60263a80af6207aca494d2e1388e44fa372889. The frozen entry says open and unformalized, consistent with the current maintained page.
The pinned FormalConjectures 422.lean, Git blob 860ad8b1f69a01da789cbe7d133789ce9924c2f0, defines a partial recursive function on positive integers. Its statements about missing values, surjectivity, growth and eventual constancy have placeholder answers and proofs marked sorry. The presence of that file does not certify totality or a solution.
The authenticated source audit is original issue #1692, comment #6157180709. That is provenance for the article, not a GCL proof certificate or protected editorial admission.
What remains
A bounded successor should calculate this recurrence through a fixed limit such as \(n=10^6\), recording the exact two input indices for each term, the largest computed value and every value below a declared threshold not observed within the prefix. A second independently written evaluator should replay a smaller overlapping range. Invalid indices must cause an explicit stop rather than being silently replaced.
A separate research task should seek a mathematical invariant establishing that both recursive arguments are always positive earlier indices. The finite computational task succeeds only if every recorded term replays exactly and the labels distinguish nonobservation from global absence. It fails upon an invalid index, mismatched term or claim that finite data prove an infinite statement. The task stops at its predetermined bound; it does not declare the Erdős problem solved.
Sources and claim boundaries
Historical problem: Erdős–Graham (1980), printed p. 83. Maintained mathematical status: Erdős Problem #422. Numerical reference: OEIS A005185. Research context: Pinn, arXiv:chao-dyn/9803012. Frozen issue: #1692, catalogue, formal interface, and authenticated RESULT/1.
The numerical prefix is independently reproducible. No finite nonobservation is described as a permanently missing value, and no source statement or formal placeholder is promoted into proof. Mathematical certification and V2 editorial admission remain separate.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1692 — 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.