Skip to content

Erdős Problem #412

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: number theory, iterated functions.

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 sum-of-divisors function \(\sigma(n)\) adds every positive divisor of an integer \(n\), including \(1\) and \(n\) themselves. For example, \(\sigma(6)=1+2+3+6=12\). One can repeat this operation: first calculate \(\sigma(n)\), then \(\sigma(\sigma(n))\), and so on. Erdős Problem 412 asks whether every two starting integers at least 2 eventually reach a common value, possibly after different numbers of steps. With \(\sigma_0(n)=n\) and \(\sigma_{r+1}(n)=\sigma(\sigma_r(n))\), the question is whether for all \(m,n\geq2\) there are nonnegative integers \(i,j\) such that

\[ \sigma_i(m)=\sigma_j(n). \]

The two indices need not agree. Once a common value occurs, all subsequent values agree after an appropriate shift. Conversely, inspecting two orbits for only finitely many steps cannot prove that they never meet. An affirmative answer would be a global coalescence statement, not the assertion that individual sequences converge to finite limits. Van Wijngaarden suggested the question to Erdős in the 1950s. The original GCL audit is issue #1682.

A small example

Direct integer arithmetic starting at \(2\) gives

\[ 2\longmapsto3\longmapsto4\longmapsto7\longmapsto8 \longmapsto15\longmapsto24\longmapsto60. \]

For instance, \(\sigma(4)=1+2+4=7\), \(\sigma(8)=1+2+4+8=15\), and \(\sigma(15)=1+3+5+15=24\). Starting at \(3\) gives \(3,4,7,8,15,\ldots\), so the first two orbits meet at \(3\): one iteration from \(2\), zero iterations from \(3\). Starting from \(5\) instead gives

\[ 5\longmapsto6\longmapsto12\longmapsto28\longmapsto56 \longmapsto120\longmapsto360. \]

For these last two starting points, \(2\) and \(5\), no intersection was found in the first nine recorded values of each orbit. That is only an observation about a declared finite computation, not a counterexample to Problem 412. The paths might merge at a much greater height.

The calculation is independently reproducible using integer divisor pairs: for every integer \(d\) with \(1\leq d\leq\sqrt{n}\) that divides \(n\), add both \(d\) and \(n/d\), counting a square-root divisor only once. Applying this rule successively produces the listed values. It also guards against a common mistake: summing only proper divisors computes \(\sigma(n)-n\), a different dynamical system. All arithmetic in these examples is exact and involves no numerical approximation.

What is known

The original printed discussion occurs in P. Erdős and R. L. Graham, Old and New Problems and Results in Combinatorial Number Theory (1980), printed page 81 of the historical scan. It explicitly credits van Wijngaarden and reports Selfridge's numerical evidence suggesting a negative answer. That statement is historical testimony about calculations, not a proved counterexample. The authors themselves do not resolve the question there.

The maintained Erdős Problems #412 entry, checked on 13 October 2026, still labels this formulation OPEN. It also references the nearby iteration problems #413 and #414. Those use different arithmetic maps, so neither a finite example nor a theorem about them automatically transfers to iterated divisor sums. This bounded source audit found no primary publication resolving the general universal intersection assertion.

There is an easy independent observation. For every \(n>1\), both \(1\) and \(n\) divide \(n\), giving \(\sigma(n)\geq n+1\). Hence every individual orbit strictly increases and eventually exceeds any fixed threshold. But this fact is not an answer: two increasing sequences can diverge without sharing any value, and increase alone does not establish coalescence either. The problem is about intersections across all starting points.

GCL's current state

The original issue #1682 locks the catalogue at teorth/erdosproblems commit 536408716724a2402bdfa7c1d764bf83d64a8c89, file data/problems.yaml, Git blob 4e60263a80af6207aca494d2e1388e44fa372889. The metadata records open informal status and unformalized solution status as of August 2025. The maintained page still reports open status. No proof is inferred from having a catalogue entry.

The issue-pinned formal interface is FormalConjectures 412.lean, blob 6ca857bddb7bdbfa2a5785896dbb1444241473db. Its theorem uses iteration of the arithmetic sum-of-divisors map together with the specialized binder called forall-eventually, written there as a mathematical binder, and an answer placeholder. Its proof is literally a placeholder. That binder requires semantic review before asserting equivalence to the historic universal formulation; a statement file is not a certification.

The authenticated issue result is authenticated original RESULT/1. Even when posted, the source report establishes provenance only. The V2 editorial ledger, not this article, determines accepted Compendium status. No Lean build, proof replay, or GCL mathematical certification was performed.

What remains

A useful bounded task is an exact audit of orbit intersections within a fixed sample: enumerate \(\sigma\) orbits starting from \(2\) through \(50\), stop after ten steps each, and record the first verified common value for every pair that meets. For pairs without an observed common value, report only that none was seen within the stated bound. The successor must include the two step indices for each positive collision and replay them from scratch.

Independently test the divisor enumerator against the prime-power identity

\[ \sigma(p^a)=1+p+\cdots+p^a =\frac{p^{a+1}-1}{p-1}. \]

The second task is to compare the exact historical quantifiers with the specialized binder and index conventions in the pinned Lean statement. Completion of these two bounded checks produces a semantic and computational fixture, not a decision about the conjecture. Falsification consists of an incorrect recorded collision, a divisor-sum mismatch, or a changed quantifier. Stop at those checks rather than claiming to resolve the infinite question from finite data.

Sources and claim boundaries

Historical primary question: Erdős–Graham 1980, printed page 81. Maintained statement and dated open status: Erdős Problem 412. Original protected audit: GCL issue #1682. Frozen source metadata: teorth catalogue. Formal interface: pinned 412.lean.

The displayed finite calculations and the elementary increasing-orbit fact are independently checkable. Selfridge's historical report is not an available proof of disjointness, and the formal file has no completed theorem proof. This article neither resolves the conjecture nor claims publication or mathematical certification.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1682 — 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.

Back to catalogue · Compendium introduction