/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/modulepublicimportFormalConjecturesUtil
[ErGr80] Erdős, P. and Graham, R., Old and new problems and results in combinatorial number
theory. Monographies de L'Enseignement Mathématique (1980).
[Pi29] Pillai, S. Sivasankaranarayana, On a function connected with $\phi(n)$. Bull. Amer.
Math. Soc. 35 (1929), 837-841.
doi:10.1090/S0002-9904-1929-04800-6
[Sh50] Shapiro, Harold N., On the iterates of a certain class of arithmetic functions. Comm.
Pure Appl. Math. 3 (1950), 259-272.
[EGPS90] Erdős, P., Granville, A., Pomerance, C. and Spiro, C., On the normal behavior of the
iterates of some arithmetic functions. Analytic number theory (Allerton Park, IL, 1989),
Progr. Math. 85 (1990), 165-204.
[Gu04] Guy, Richard K., Unsolved problems in number theory. Third edition, Springer (2004),
Problem B41.
f n is $f(n) = \min{k \geq 1 : \phi_k(n) = 1}$, where $\phi_1 = \phi$ is Euler's totient
function and $\phi_k(n) = \phi(\phi_{k-1}(n))$. As in the source, $k$ starts at $1$, so
$f(1) = 1$. Every iterate of $\phi$ at $0$ is $0$, so sInf ∅ = 0 gives the junk value
$f(0) = 0$.
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?
We ask for a distribution function $F$ (non-decreasing, with $F(-\infty) = 0$ and
$F(+\infty) = 1$) such that, for every continuity point $c$ of $F$, the set
${n : f(n)/\log n \leq c}$ has natural density $F(c)$. For $n \leq 1$ the quotient is $0$ in
Lean, which does not affect densities. Erdős, Granville, Pomerance and Spiro [EGPS90] proved
that the answer is yes, conditional on a form of the Elliott–Halberstam conjecture.
We read this as: is there a constant $\alpha$ such that, for every $\epsilon > 0$, the set of
$n$ with $|f(n)/\log n - \alpha| < \epsilon$ has natural density $1$? Erdős, Granville,
Pomerance and Spiro [EGPS90] proved that, conditional on a form of the Elliott–Halberstam
conjecture, $f(n)$ has normal order $\alpha \log n$ for some constant $\alpha > 0$, so that the
answer is yes under this hypothesis.
Pillai [Pi29] proved that, for all $n \geq 2$,
$$\left\lfloor \frac{\log n - \log 2}{\log 3} \right\rfloor + 1 \leq f(n) \leq
\left\lfloor \frac{\log n}{\log 2} \right\rfloor + 1.$$
These are Theorems I and III of [Pi29]; Pillai's function $R(n)$ is the least $r$ with
$\phi_r(n) = 1$, which is $f(n)$. The lower bound is attained at $n = 2 \cdot 3^k$, and
$f(2^k) = k$ (Erdos408.f_two_pow), so the upper bound cannot be replaced by $f(n) < \log_2 n$.
The third question asks what can be said about the largest prime factor $P^+(\phi_k(n))$ when,
say, $k = \log\log n$; it is open-ended and is not formalised. The site remarks that it is likely
true that, if $k \to \infty$ however slowly with $n$, then $P^+(\phi_k(n)) \leq n^{o(1)}$ for
almost all $n$.
Ford, Konyagin and Luca [FKL10, Theorem 5] proved that for every $\epsilon > 0$ and $\delta > 0$
there is an integer $k$ such that, for all large $x$, at least $(1 - \epsilon)x$ integers
$n \leq x$ satisfy $P^+(\phi_k(n)) \leq x^{\delta}$. Since $P^+(\phi(m)) \leq P^+(m)$, this gives
the remark above for every $k = k(n) \to \infty$.