ERDŐS/DAILY ▸

← back to the ledger

ERDőS #412 · PARTIAL

Erdős problem 412, wave 9e

Access and re-verification date: 2026-07-28 UTC.

0. Mandatory live-page gate

(b) Source-verified. I fetched https://www.erdosproblems.com/412, its LaTeX view, and its discussion thread through the Bright Data browser. I did not infer the statement from the stale tracker metadata and did not use datacenter curl for the live-page gate.

The current statement, copied verbatim from the page's LaTeX view, is:

Let $\sigma_1(n)=\sigma(n)$, the sum of divisors function, and $\sigma_k(n)=\sigma(\sigma_{k-1}(n))$.

Is it true that, for every $m,n\geq 2$, there exist some $i,j$ such that $\sigma_i(m)=\sigma_j(n)$?

(b) Source-verified. The stop gate did not fire:

All known-result text on the live page

(b) Source-verified page record, not independently promoted to a theorem. The page attributes the conjecture to van Wijngaarden via Erdős in the 1950s, interprets it as eventual uniqueness of the iterated-\(\sigma\) orbit, reports Selfridge's contrary numerical evidence, records Erdős and Graham's pessimism about near-term proof, and points to Problems 413 and 414.

Both live comments

(b) Source-verified page record. The site warns that comments are the responsibility of their users and are not verified.

  1. Dogmachine, 17:03 on 15 Feb 2026:

The analogous assertion for Euler's totient function is said to be trivial.

  1. Dogmachine, 17:08 on 09 Aug 2025:

The commenter predicts that \(m=5,n=2\) already disprove the assertion and says there is virtually no evidence supporting it.

(c) Structural-unverified. The second comment supplies no invariant or uniform proof. I therefore use \(2\) versus \(5\) as a computational target, not as an established counterexample.

1. Claim labels

named primary source, without re-proving all of that source.

estimate; never used as a theorem.

standalone checker; it is not a uniform statement about infinite orbits.

2. Primary-source and literature audit

Original formulations

  1. (b) P. Erdős, Some unconventional problems in number theory, Acta

Math. Acad. Sci. Hungar. 33 (1979), 71–80, author-archive PDF. On printed p.71 Erdős attributes the question to van Wijngaarden in the early 1950s, states the “essentially only one sequence” formulation, and reports that Selfridge and others made computer experiments and believed it false. Local PDF SHA-256: a4703a104adcbbde0ed605c9ff81379adee8b7ceda3714ea455b5b68ae720dfd.

  1. (b) P. Erdős and R. L. Graham, *Old and New Problems and Results in

Combinatorial Number Theory* (1980), printed p.81, Graham author-archive scan. It gives the same coalescence question, reports Selfridge's contrary numerical evidence, and contains the sentence quoted on the live page. Local PDF SHA-256: 0cbf0c32f0ab1e1c71db5121a88bac905bf976c4a6ab6bb6d7d9cf9ddd184ed3.

  1. (b) P. Erdős, A. Granville, C. Pomerance, and C. Spiro, *On the

Normal Behavior of the Iterates of Some Arithmetic Functions, in Analytic Number Theory* (1990), pp.165–204, Pomerance author copy. Printed p.169 lists the present question as statement (vi), followed by “We can neither prove nor disprove any of these statements.” Local PDF SHA-256: 7e95622ae683439cb31ef12949ab35a744cf3e1d32bc14d4d28d4b6deaff81fd.

The directly relevant computation

  1. (b) G. L. Cohen and H. J. J. te Riele, *Iterating the

Sum-of-Divisors Function*, Experimental Mathematics 5 (1996), 91–100, DOI 10.1080/10586458.1996.10504580, CWI final-version PDF. The paper explicitly calls the present assertion statement (vi) and says the authors do not believe it.

(d), as reported by that primary source rather than rerun in full here. Cohen and te Riele found 21 distinct orbit trees for starting values at most 200 and checked that the trees remained distinct through their first terms exceeding \(10^{200}\). Their tree representatives were \[ 2,5,16,19,27,29,33,49,50,52,66,81,85,105,146,147,163,170,189,197,199. \] They also reported 64 trees for starts at most 1000 with cutoff \(10^{100}\). Their wording is explicitly conjectural beyond the finite cutoff. Local PDF SHA-256: 7686998962fe207f5fd37e4f6f21c27386afd558d5075af90a7c54b2e3c6e12d.

Later leads checked

  1. (b) The current arXiv record

arXiv:2102.09941v2, revised 2025-12-25, is titled On Congruences for Iterates of the Sum--Power Divisor Function and Conditional Implications for the Riemann Hypothesis. It addresses the different modular question of whether a fixed \(n\) divides every iterate \(\sigma^k(n)\); it does not prove or disprove orbit coalescence.

(a)+(b) Reliability warning. The current preprint asserts that \(\sigma^k(6)\equiv0\pmod 6\) for every odd \(k\). Directly, \[ \sigma(6)=12,\qquad \sigma^2(6)=28,\qquad \sigma^3(6)=56\equiv2\pmod6, \] so that assertion is false. I use no theorem from this preprint.

  1. (d) External cross-check only. The live page's OEIS links are

A007497, the orbit starting at 2, and A051572, the orbit starting at 5. After the independent computation below, its prefixes agreed with those database tables. Neither table is an input to the standalone checker.

  1. (c) Literature-search miss, not a theorem. I searched exact phrases

from the problem, the 1990 statement (vi), the Cohen–te Riele title and DOI, arXiv full text, and forward citations returned by OpenAlex. I found later work on multiperfect numbers, congruences, and other iterated divisor functions, but no later primary source proving or disproving the uniform coalescence statement or proving that the \(2\)- and \(5\)-orbits are forever disjoint.

3. Elementary reduction

Write

\[ x_i=\sigma^i(2),\qquad y_j=\sigma^j(5),\qquad i,j\geq0, \]

where the superscript denotes iteration and the zeroth iterate is included only to make the computation stronger than the page's positive-index formulation.

Lemma 1: strict growth — (a)

For every \(n\geq2\),

\[ \sigma(n)\geq n+1>n, \]

because \(1\) and \(n\) are distinct positive divisors. Thus every orbit in the problem is strictly increasing and unbounded.

Lemma 2: merger is permanent — (a)

If \(\sigma^i(m)=\sigma^j(n)\), then applying the same function \(t\) more times gives

\[ \sigma^{i+t}(m)=\sigma^{j+t}(n)\qquad(t\geq0). \]

Thus the problem asks whether the functional graph of \(\sigma\) on \(\{2,3,\ldots\}\) has only one forward end/component.

Lemma 3: a finite cutoff is exact — (a)

Fix \(X\). Compute each of two orbits through its first term greater than \(X\). Strict growth proves that every later term is also greater than \(X\). Therefore, comparing the two finite prefix sets proves or disproves the existence of a common orbit value at most \(X\); there is no omitted case below the cutoff.

This is the sole logical bridge from the computation to the finite theorem below. It does not turn any finite cutoff into an infinite counterexample.

4. Independently reproduced finite theorem

Method — (d)

The standalone checker erdos412_wave9e_reverify.py has no network access and contains no downloaded orbit terms. Starting from only 2 and 5, it repeats the following for every transition:

  1. PARI/GP factor produces a complete prime-power factorisation of the

current term.

  1. PARI/GP isprime separately proves every reported base prime.
  2. Python multiplies the prime powers back to the current term.
  3. Python, independently of PARI's sigma, evaluates

\[ \sigma\left(\prod p^e\right) =\prod\frac{p^{e+1}-1}{p-1}. \]

  1. Python checks exact division, strict growth, the boundary hashes, and set

disjointness.

Every individual factorisation is capped at 30 seconds. This final run used Python 3.12.3 and PARI/GP 2.15.4.

Result — (d)

Finite theorem. For all \(i,j\geq0\),

\[ \sigma^i(2)\leq10^{342}\ \text{and}\ \sigma^j(5)\leq10^{342} \quad\Longrightarrow\quad \sigma^i(2)\ne\sigma^j(5). \]

Equivalently, the two orbits have no common value at most \(10^{342}\). This extends the \(2\)-versus-\(5\) part of Cohen–te Riele's \(10^{200}\) computation, but it does not extend their broader 21-tree computation.

| Seed | Terms \(\leq10^{342}\) | Last iteration \(\leq X\) | First iteration \(>X\) | Last/first digits | |---:|---:|---:|---:|---:| | 2 | 421 | 420 | 421 | 342 / 343 | | 5 | 420 | 419 | 420 | 342 / 343 |

The exact audit fingerprints are:

| Seed | SHA-256 of last term \(\leq X\) | SHA-256 of first term \(>X\) | SHA-256 of all factorisation records | |---:|---|---|---| | 2 | 78e42aa96ab96630ef476d290c7690315fdfd829bb85ad9840cb8cda05e6b712 | ff2ee3128e1c818b2f5fb64e01721e1fd9c9d073f2e8df2eca8f16becd677022 | c07970da7175ec2dfe767280f794e0d92716e95414f387e7eca665daa7b8cd6b | | 5 | d795f62084bbba622735298321487de89422fa9b53aa4bbbd3f7a8280b7f0b11 | 40b6a976239526b3c949821874147e37d6155a1437ebf4253c4382f1adb916b7 | a9b825f657bc292b0efd6c004bdb8b575fd518b5167c0ecf3ea3da78b8329884 |

(d) The run checked 841 complete transitions. The largest prime factor encountered had 132 bits in the \(2\)-orbit and 187 bits in the \(5\)-orbit. The maximum numbers of distinct prime factors in a term were 71 and 73, respectively. Set intersection returned zero.

Exact boundary values — (d)

For seed 2,

\[ \begin{aligned} x_{420}={}&758537157807219117581784517966775287734241688697974416469312831034202543216410799449923583738966112889421872931134679783613943600746608577509079234355721464903953401488745164904944331801683587942150902537689522764156238445722730196966391462377720255945924488869510640891743282461576555087018027081388217435644137440380568207360000000000000000,\\ x_{421}={}&6111800934105099482729680610472095168054044918315565226214675825272877069682512753023185829976558863661881050473366548726691746272265963538021522917501087819111185989299894794498557756934660962508060881706468143435018188029026071792748753425316755824135226825169416958261329711252854873271720017313270883713171006967007674368000000000000000000. \end{aligned} \]

Here \(x_{420}<10^{342}<x_{421}\).

For seed 5,

\[ \begin{aligned} y_{419}={}&543904815928815324130591315541088973995378635409642474671895302144783250488052353605362403439063377876676514851430173543940615877562990161104182094464684700929872609093049004800838709213440439461673232682590806329495593716892739516472297051014934203973541638230781612159795049469993907674155303142555733045023482725953623839211520000000000000,\\ y_{420}={}&4140059485434272079639012051478023485615013791569217340775823938210474068648639417951793509034203744496511923328352501689999130002308377400351865854807397366389879596132134801473948909931698184118127559389827225467698834949581996140252942919732938403783200066585806495595254784489935702741802710327252176799802026366186401510195200000000000000. \end{aligned} \]

Here \(y_{419}<10^{342}<y_{420}\).

5. Exact computation wall

(d) Extending the fresh \(5\)-orbit computation requires evaluating \(\sigma(y_{420})\). A full PARI factorisation of \(y_{420}\) exceeded the 30-second per-step cap. The checker reproducibly removes 52 distinct proved-prime bases by partial factorisation through \(10^8\), verifies their product with the remaining factor, and leaves the proved-composite 115-digit cofactor

\[ C={4656986927188253600039163797619899639277935785221870960736549181501515649171712041530938765268222515422848178662589}. \]

(d) Thus the exact missing computation for this implementation's next step is a complete factorisation of \(C\), or an independent certificate of \(\sigma(y_{420})\) that avoids that factorisation. Factoring \(C\) would extend only one finite prefix; later iterates can introduce new hard cofactors.

(c) Cost estimate. The official CADO-NFS documentation says that its GNFS implementation is aimed at numbers above 85 digits, and an Intel engineering benchmark page reports 120-digit semiprimes in under two hours on its many-core system. For this 115-digit cofactor, a planning range of roughly 10–100 modern core-hours is reasonable, with a much cheaper outcome possible if ECM finds an unbalanced factor. At a notional $0.04–$0.10 per core-hour, that is roughly $0.40–$10. This is an engineering estimate, not a certified complexity bound, so I did not launch it on this VM.

6. Exact mathematical wall

(a) A finite computation cannot resolve the page's quantifiers. Even if the two prefixes are disjoint through \(10^{342}\), their first common value could be larger.

(a) A fixed congruence-state automaton is not automatically available: the function \(\sigma\) is not determined by a residue class. For example, \(2\equiv6\pmod2\), but \(\sigma(2)=3\) is odd whereas \(\sigma(6)=12\) is even. Any successful modular invariant would therefore need information about factorisation structure, not merely the current integer modulo a fixed modulus.

(b)+(c) The analytic results in Erdős–Granville–Pomerance–Spiro concern normal or almost-all behavior and fixed-depth iterates. They do not provide the uniform, all-time control of the two exceptional deterministic orbits needed here.

(a) Exact missing lemma. To turn the \(2,5\) evidence into a counterexample, one needs an invariant or monotone structural quantity preserved by every \(\sigma\)-step that separates the two orbits, or another uniform theorem proving

\[ \sigma^i(2)\ne\sigma^j(5)\qquad\text{for all }i,j\geq0. \]

Conversely, a positive solution needs a global coalescence theorem, for example a proof that every orbit eventually hits one distinguished orbit. Neither requirement follows from any finite factorisation table.

7. Reproduction

Run:

python runs/erdos412_wave9e_reverify.py

(d) The final run returned PASS in 47.60 wall-seconds, used 45.97 user CPU-seconds, and peaked at 26,836 KB RSS. The checker SHA-256 is c77cf72dd395f735ee926cccd9f2e75d7ec32d227eef364efd01d2441cd75ecf.

Its terminal conclusion is:

PASS: sigma^i(2) != sigma^j(5) whenever both values are at most 10^342 (also checked at i=j=0).

PARTIAL: Independently proved computationally that the sigma-orbits of 2 and 5 have no common value at most 10^342, extending their published 10^200 separation; no uniform invariant was found, and the next fresh 5-orbit step leaves a 115-digit composite cofactor.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger