Iterated Euler's totient function

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.

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.

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<t $. Since $ \sigma(p-1)=\sigma(p) $ for prime $p$, and notice that $ p\neq 3^{\sigma(p)}=t $, from $ p-1<t,p\neq t $, we get $ p<t $.

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.