# Iterated Euler's totient function

Let $\phi(n)$ be the Euler totient function: $$\phi(2)=1 \;,\; \phi(11)=10 \;,\; \phi(12)=4\;,$$ etc. Define $\Phi(n)$ to be the number of iterations $k$ so that $\phi^k(n)$ reaches $1$. For example, $\Phi(25)=5$ because $\phi(25)=20$ and continuing, it takes $5$ applications to reach $1$: $$25,20,8,4,2,1 \;.$$ Another example: $\Phi(113)=7$: $$113,112,48,16,8,4,2,1 \;.$$ Here is a plot of $\Phi(n)$:

Red curve: $0.43 + 1.22 \ln( n )$.
$\Phi(n)$ is fit quite well (and well beyond what's shown above) by $c \ln(n)$.

Two questions:

Q1. What explains the logarithmic growth, at a high-level?

Q2. What explains the constant $c \approx 1.22$?

Likely both of these questions are answered in the literature.

• See whether this helps you: oeis.org/A003434 – Rohan Dec 4 '17 at 11:58
• @Rohan: Thanks! Here's one fact from that OEIS entry: "Pillai proved that log(n/2)/log(3) + 1 <= a(n) <= log(n)/log(2) + 1," where a(n) is what I call $\Phi(n)$. – Joseph O'Rourke Dec 4 '17 at 12:09
• (@stefan4024: I would prefer the title not use LaTeX so it can be cited elsewhere.) – Joseph O'Rourke Dec 4 '17 at 12:13
• For the fun of it: Iterated phi sequence, a coding challenge to output $\Phi(n)$ from $n=2$ to $n=100$. – Simply Beautiful Art Dec 4 '17 at 15:53
• I don't think unicode phi symbol is better than "iterated phi(n) function". But n in the title is awkward. I think the best (most citable / searchable) is "iterated Euler totient function" or "Iterated phi function" or "Iterated Euler's phi function" – 6005 Dec 4 '17 at 19:10

Note that $\phi(n)$ is even (for $n\ge3$), and if $n$ is even then $\phi(n)\le n/2$. This immediately gives you Pillai's logarithmic upper bound.

• This is quite insightful, and certainly makes the $\alpha \log n$ conjecture that @lhf found plausible. – Joseph O'Rourke Dec 5 '17 at 0:38

Erdős et al. say this in On the Normal Behavior of the Iterates Of some Arithmetic Functions:

[...] it is easy to see that the set of numbers of the form $k(n)/ \log n$ is dense in $[1/ \log 3,1/ \log 2]$. What is still in doubt about $k(n)$ is its average and normal behavior. We conjecture that there is some constant $\alpha$ such that $k(n) \sim \alpha \log n$ on a set of asymptotic density $1$.

Here, $k(n)$ is what the OP calls $\Phi(n)$.

The original paper was published in 1990. Perhaps it is still the state of the art.

• The other authors of that paper are still around and active. Maybe one of them would know whether there has been any progress. – Gerry Myerson Dec 5 '17 at 2:58

I would like to show Pillai's lower bound. Here we use $$\varphi^*(n)$$ to denote $$\Phi(n)$$ because of the famous log-star function ($$\log^*$$) in complexity.

To get started, we need a special variety of Euler's totient function $$\hat\varphi$$, which is $$\varphi$$ without considering 2, namely $$\hat \varphi(x):=\begin{cases}\varphi(x), x\text{ odd}\\ 2\cdot\varphi(x), x\text{ even}\end{cases}$$.

When $$k$$ goes sufficiently large(actually it is just $$\varphi^*(x)$$), it is easy to see that $$\varphi^k$$ approaches $$1$$ and $$\hat\varphi^k$$ approaches some power of $$2$$. Let's denote it as $$2^{\sigma(x)} \le2^k=2^{\varphi^*(x)}$$. The inequility is obvious. Then we make a claim.

Claim. For all odd number $$x$$, there holds $$x\le 3^{\sigma(x)}$$. The equality holds iff $$x$$ is some power of $$3$$.

Proof of the claim. Obviously $$\sigma(2)=\sigma(3)=1, \sigma(3^k)=k$$. And it is also easy to check that $$\sigma(pq)=\sigma(p)+\sigma(q)$$. So we just need to deal with the prime numbers. By induction, we consider the prime $$p>3$$. We have known that $$p-1\le 3^{\sigma(p-1)}=:t$$, and the equality never holds, so $$p-1. Since $$\sigma(p-1)=\sigma(p)$$ for prime $$p$$, and notice that $$p\neq 3^{\sigma(p)}=t$$, from $$p-1, we get $$p.

Eventually the final step.

When $$x$$ is odd, $$\varphi^*(x)\ge\sigma(x)+1\ge\log_3n+1$$.

When $$x$$ is even, we write $$x=2^d\cdot c, d\ge1, c\text{ odd}$$, then $$\varphi^*(x)\ge \sigma(x)=d+\sigma(c)\ge d+\log_3c\ge1+ \log_3{x\over2}$$. Easy to check the equality holds iff $$x =2\cdot3^k$$ for some $$k$$.

Here the proof ends.

The proof comes from a proof sketch by Deng Mingyang(moorhsum), the IMO 2019 gold medal winner from China, posted on Zhihu(Chinese), a chinese version of Quora. I prove the claim here which the sketch not contains. I am curious about why to construct such $$\hat\varphi$$ and make such a claim.