Hello everyone. This is my first blog on codeforces.

Coming to the topic, consider the task where you are given an integer $$$n$$$ and you are asked to find the minimum value of $$$k$$$ such that $$$\phi(\phi(\phi...\phi(n)))$$$ $$$= 1$$$ (where $$$\phi$$$ is applied $$$k$$$ times on $$$n$$$ in a nested manner and $$$\phi$$$ is the euler totient function). This task can be solved, but for now let's focus on finding an upperbound for $$$k$$$.

We have,

where $$$n = p_1^{a_1} \cdot p_2^{a_2} \cdot ... p_m^{a_m}$$$ and $$$p_1,p_2...,p_m$$$ are prime factors of $$$n$$$. Proof can be found here.

Now, if $$$n$$$ is even, $$$2$$$ is a prime factor of $$$n$$$ so $$$\phi(n)$$$ $$$\le$$$ $$$\frac{n}{2}$$$ and if $$$n$$$ is odd and $$$n>1$$$, $$$\phi(n) < n$$$ and $$$\phi(n)$$$ is even. So we can safely say that $$$\phi(\phi(n)) \le \frac{n}{2}$$$ for all $$$n>1$$$. Repeating this process, it is obvious that after applying $$$\phi$$$ for $$$2 \cdot \lceil \log_2(n) \rceil$$$ times on $$$n$$$, we have $$$\phi(\phi(\phi...\phi(n)))$$$ $$$= 1$$$. So we have $$$k \le 2 \cdot \lceil \log_2(n) \rceil$$$.

We can find an even tighter bound using the fact that $$$\phi(n)$$$ is even for all $$$n \ge 3$$$. So for any $$$n \ge 3$$$, $$$\phi(n)$$$ is even and $$$\phi(\phi(n)) \le \frac{n}{2}$$$, $$$\phi(\phi(\phi(n))) \le \frac{n}{4}$$$, $$$\phi(\phi(\phi(\phi(n)))) \le \frac{n}{8}$$$ and so on. Thus after applying $$$\phi$$$ for $$$\lceil \log_2(n) \rceil$$$ times on $$$n$$$, we have $$$\phi(\phi(\phi...\phi(n)))$$$ $$$= 1$$$. So we have $$$k \le \lceil \log_2(n) \rceil$$$.

Please excuse me for my grammatical errors and I hope atleast someone finds this interesting.