Distribution of $f(n)=\min\{k:\phi_k(n)=1\}$, the totient iteration length (Erdős #408)
Statement
Let $\phi$ be the Euler totient function and let $\phi_k$ denote its $k$-fold iterate: $\phi_1(n)=\phi(n)$ and $\phi_k(n)=\phi(\phi_{k-1}(n))$. Define the totient iteration length $$f(n)=\min\{k:\phi_k(n)=1\},$$ the number of times one must apply $\phi$ to reach $1$. (i) Does $f(n)/\log n$ possess a distribution function? (ii) Is $f(n)/\log n$ almost always equal to a single constant? (iii) What can be said about the size of the largest prime factor of $\phi_k(n)$ when, e.g., $k=\log\log n$?
Acceptance. FULLY RESOLVES: an unconditional proof settling the main questions — that $f(n)/\log n$ has a distribution function and is almost always equal to an explicit constant $\alpha$ (identifying $\alpha$), i.e. removing the Elliott–Halberstam hypothesis from the [EGPS90] result — together with a proof of the largest-prime-factor statement (iii); a full written proof (Lean/Coq welcome). ADVANCES (each itself checkable): an unconditional proof of the distribution / almost-sure-constant claim under a weaker or different hypothesis than the Elliott–Halberstam form used by [EGPS90]; a proof of the $n^{o(1)}$ largest-prime-factor bound for an explicit range of $k$; a strict, proven improvement of the Pillai bounds $\log_3 n < f(n) < \log_2 n$; or a reproducible large-scale computation of $f(n)$ that materially extends OEIS A049108, reports the empirical distribution of $f(n)/\log n$ and a strong numerical estimate of the constant, with the code and the range certified. Deliver the proof and/or the search code plus the range covered and the measured statistics.
Background
From Erdős–Graham [ErGr80, p.80], and discussed as problem B41 in Guy [Gu04]; listed as open on erdosproblems.com/408 (fetched 2026-07-13, status 'open', tagged 'number theory | iterated functions'), no prize. The sequence $f(n)$ (the totient iteration length, sometimes called the 'class' of $n$) is OEIS A049108. Known results: Pillai [Pi29] first studied $f$ and proved $\log_3 n < f(n) < \log_2 n$ for all large $n$ (logarithms to bases $3$ and $2$), pinning its order of magnitude to $\Theta(\log n)$. Shapiro [Sh50] proved that $f$ is essentially multiplicative. Toward (i)–(ii), Erdős, Granville, Pomerance, and Spiro [EGPS90] proved that $f(n)/\log n$ DOES have a distribution function and IS almost always constant — but only conditionally, assuming a form of the Elliott–Halberstam conjecture; the unconditional statement is open. For (iii) it is expected that if $k\to\infty$ however slowly with $n$, then for almost all $n$ the largest prime factor of $\phi_k(n)$ is $\le n^{o(1)}$. The problem is not formalised in the DeepMind repository. Attacker's tool: large-scale sieve computation of $f(n)$ (extending A049108) to measure the empirical distribution of $f(n)/\log n$ and the putative constant, combined with analytic number theory (anatomy-of-integers / Elliott–Halberstam-type inputs) to remove the conditional hypothesis of [EGPS90] or to establish the largest-prime-factor claim.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #408 (T. F. Bloom) | website |
| REF-02 | OEIS A049108 — a(n) = number of iterations of Euler phi to reach 1 | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.