Problem 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$?
Categories:
Number Theory Iterated Functions
Progress
Pillai [Pi29] was the first to investigate this function, and proved\[\log_3 n < f(n) < \log_2 n\]for all large $n$. Shapiro [Sh50] proved that $f(n)$ is essentially multiplicative.Erdős, Granville, Pomerance, and Spiro [EGPS90] have proved that the answer to the first two questions is yes, conditional on a form of the Elliott-Halberstam conjecture.
It is likely true that, if $k\to \infty$ however slowly with $n$, then for almost all $n$ the largest prime factor of $\phi_k(n)$ is $\leq n^{o(1)}$.
This is discussed in problem B41 of Guy's collection [Gu04].
Source: erdosproblems.com/408 | Last verified: January 14, 2026