Problem: Prove that if $n$ and $k$ are positive integers
satisfying $\varphi^k(n) = 1$, then $n \le 3^k$.
(Here $\varphi^k$ denotes $k$ applications of the Euler phi function.)

Solution: The main observation is that the exponent of $2$ decreases
by at most $1$ with each application of $\varphi$.
This will give us the desired estimate.

Define the \emph{weight} function $w$ on positive integers as follows: it satisfies
\begin{align*}
  w(ab) &= w(a)+w(b); \\
  w(2) &= 1; \quad\text{and} \\
  w(p) &= w(p-1) \quad \text{for any prime $p > 2$}.
\end{align*}
By induction, we see that $w(n)$ counts the powers of $2$
that are produced as $\varphi$ is repeatedly applied to $n$.
In particular, $k \ge w(n)$.

From $w(2) = 1$, it suffices to prove that $w(p) \ge \log_3 p$ for every $p > 2$.
We use strong induction and note that
\[
 w(p) = w(2) + w\left( \frac{p-1}{2} \right)
 \ge 1 + \log_3(p-1) - \log_3 2 \ge \log_3 p
\]
for any $p > 2$. This solves the problem.

\begin{remark*}
One can motivate this solution through small cases $2^x 3^y$
like $2^x 17^w$, $2^x 3^y 7^z$, $2^x 11^t$.

Moreover, the stronger bound \[ n \le 2 \cdot 3^{k-1} \] is true and best possible.
\end{remark*}