Problem 408

Statement

Let $\phi(n)$ be the Euler totient function and $\phi_k(n)$ be the iterated $\phi$ function, so that $\phi_1(n)=\phi(n)$ and $\phi_k(n)=\phi(\phi_{k-1}(n))$ . Let

f(n) = \min \{ k : \phi_k(n)=1\}.

Does $f(n)/\log n$ have a distribution function? Is $f(n)/\log n$ almost always constant? What can be said about the largest prime factor of $\phi_k(n)$ when, say, $k=\log\log n$ ?

Source: erdosproblems.com/408

Number theory
Iterated functions

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

Solved: an accepted partial claim settles both parts, and the open-ended third question does not block the standing. Bloom's catalog labeled the problem OPEN (page last edited 30 September 2025). Its commentary credits [EGPS90] with a yes to the first two questions under a form of the Elliott--Halberstam conjecture. That conditional theorem is the claim on the Erdős–Granville–Pomerance–Spiro page. Its scope is conditional, and it derives nothing for the standing. Plasma AI's 2026 preprint and Lean formalization claim the first two questions without hypothesis; that claim, on the Plasma AI page, is accepted on this corpus's rebuild, Comparator check and kernel replay of the formalization and a graded review of its statements. The third question, open-ended, is answered in the form the erdosproblems.com commentary expects by Ford, Konyagin and Luca [FKL10, Theorem 5], by a deduction that [PAI26, Proposition 7.1] records and the Standing restates.

EGPS90: Erdős, P. and Granville, A. and Pomerance, C. and Spiro, C., On the normal behavior of the iterates of some arithmetic functions. Analytic number theory (Allerton Park, IL, 1989) (1990), 165-204.
ErGr80: Erdős, P. and Graham, R., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathematique (1980).
Gu04: Guy, Richard K., Unsolved problems in number theory, third edition, Problem Books in Mathematics, Springer (2004), xviii+437 pp.; B41 "Iterations of $\phi$ and $\sigma$ ", printed pp. 147--148: the class $k(n)$ , the least $k$ with $\phi_k(n)=1$ , Pillai's bounds between $\ln n/\ln 3$ and $\ln n/\ln 2$ , the density of $k(n)/\ln n$ in $[1/\ln 3,1/\ln 2]$ , the question of its average and normal behavior, and the [EGPS90] conjecture of a normal order $\alpha\ln n$ , which Guy records as proved there under the Elliott--Halberstam conjecture; the hypothesis [EGPS90] uses is a strong form of that conjecture, stated on its claim page (Erdős, Granville, Pomerance and Spiro, 1990). Library home: Guy 2004.
FKL10: Ford, Kevin and Konyagin, Sergei V. and Luca, Florian, Prime chains and Pratt trees. Geom. Funct. Anal. (2010), 1231-1258. Library home: Ford, Konyagin and Luca 2010.
PAI26: Plasma AI, The normal order of the number of iterations of Euler's function, preprint (2026), with a Lean formalization, at https://github.com/plasma-ai/erdos-408. Library home: plasma-ai 2026.
Pi29: Pillai, S. Sivasankaranarayana, On some functions connected with $\phi(n)$ . Bull. Amer. Math. Soc. (1929), 832-836.
Sh50: Shapiro, Harold N., On the iterates of a certain class of arithmetic functions. Comm. Pure Appl. Math. (1950), 259-272.

Problem 408

Statement

Status

Proof claims

Discussion