OPEN
This is open, and cannot be resolved with a finite computation.
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$?
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].
View the LaTeX source
This page was last edited 30 September 2025.
Additional thanks to: Zachary Chase
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #408, https://www.erdosproblems.com/408, accessed 2026-01-16
