#waitingforv_Enhance

Sorry, was check TSTST scores for transcription errors 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 $w(ab) = w(a) + w(b)$, $w(2) = 1$, and $w(p) = w(p-1)$ for any prime $p$. 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)$. So, it suffices to prove that $w(p) \ge \log_3 p$ for every $p$. This is certainly true for $p = 2$. For any other $p$, 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.

I had a solution which I believe was somewhat different than the other approaches, which is outlined as follows. Define a function $\kappa(n)$ to be multiplicative satisfying $\kappa(p^n)=\phi(p^n)$ for $p\le 3$ and $\kappa(p^n)=p^{n-1}(p-1)\cdot \frac{3}{2}$ for $p\ge 5$. We also define the relation $x \text{ R }y$.to be true if: $v_2(x)+v_3(x)\ge v_2(y)+v_3(y)$ $v_3(x)\le v_3(y)$ $v_p(x)=v_p(y)$ for $p\ge 5$. We claim that if $x\text{ R }2y$, then $\phi(x)\text{ R } \kappa(2y)$. Using this, we show that if $\phi^{r}(2n)=1$, then $\kappa^{r}(2n)=1$. But $\kappa(n)\ge \frac{1}{3} n$, which easily implies the result.

I must be in delirium.

There must be something wrong here, cuz $n = 2 \cdot 3^{k-1}$ solves the equation.

v_Enhance wrote: Sorry, was check TSTST scores for transcription errors Define the \emph{weight} function $w$ on positive integers as follows: it is completely multiplicative, satisfies $w(2) = 1$, and $w(p) = w(p-1)$ for any prime $p$. 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)$. "it is completely multiplicative" Maybe "it is Logarithmic".

You're correct, of course. Thanks! I'll fix that in the official solutions.

angiland wrote: There must be something wrong here, cuz $n = 2 \cdot 3^{k-1}$ solves the equation. $n=2\cdot 3^{k-1}$ < $ 3^{k}$ .

Of course. I wrote that in response to mssmath' attempt of showing $n \leq (\frac{7}{3})^k$, but he/she has deleted the original post

My solution during the actual TSTST is a somewhat refined version of the ones already posted and provides the best possible bound on $n$. Let $\varphi^k(n)=\underbrace{\varphi( \varphi( \dots \varphi(}_{k\ \text{times}} n) \dots ))$. Define $f:\mathbb{N}/ \{1\}\rightarrow \mathbb{N}$ so that $f(n)$ is the number of iterations of the Euler function required to obtain $2$ starting from $n$ (it is obvious that this number exists and is unique as $\varphi (k)$ is even and $\varphi(k)<k$ for $k\ge 3$). So $\varphi^{f(n)}(n)=2$. Take $f(2)=0$. Lemma: If $n$ is even, $n=2^kp_1^{\alpha_1}...p_t^{\alpha_t}$, we have $f(n)=k-1+\alpha_1f(p_1)+...+\alpha_tf(p_t)$. If $n$ is odd, $n=p_1^{\alpha_1}...p_t^{\alpha_t}$, we have $f(n)=\alpha_1f(p_1)+...+\alpha_tf(p_t)$ Remark: This implies $f(ab)=f(a)+f(b)$ if at least one of $a$ and $b$ is odd and $f(ab)=f(a)+f(b)+1$ otherwise.

Lemma: If $n$ is even, $n\le 2\cdot 3^{f(n)}$. If $n$ is odd, $n\le 3^{f(n)}$.

Returning to the original problem, $\varphi^k(n)=1$ implies $f(n)\le k-1$. By the previous lemma, if $n$ is odd, $n\le 3^{k-1}$ and if $n$ is even, $n\le 2\cdot 3^{k-1}$.

Note that, with each application on totient, the power of 2 can be decreased by at most 1. So, it makes sense to investigate how many powers of 2 individual numbers can make. For example, take $7$. $\phi(7)=6=2*3$, so it makes 1 $2$. After another application, $\phi(3)=2$, which creates another 2. In total, $7$ will create two $2$s after iteratively taking its phi. Let the amount of 2s a number can make be $f(k)$. It is not hard to see that $f(ab)=f(a)+f(b)$, since we can treat the two components separately. Furthermore, the amount of totients necessary to turn a number into 1 is at least $f$, so it remains to show that $f(x)\ge \log_3 x$. This follows from induction, as $f(ab)=f(a)+f(b)\ge \log_3(ab)$ if $x$ is composite. And, if $x$ is a prime more than 2, $f(x)=f(x-1)\ge \log_3(x-1)$. $2|x-1$, so the RHS is noninteger, so $f(x)\ge \lceil\log_3(x-1)\rceil\ge \log_3 x$, as desired.

Great problem that explores the depth of the totient function. Note that the exponent of $2$ in the prime factorization of $n$ decreases by at most one with each application of $\varphi$. Therefore, it suffices to show that the number of $2$s generated by repeating applying $\varphi$ is at least $\log_3n$. To this end, define a function $f$ that performs the same function as $\varphi$, except it does not decrease the exponent of $2$ in $n$. (For example, $f(2^2 \cdot 5^6) = 4/5 \cdot 2^2 \cdot 5^6$ ). Now it is easy to observe that $f$ is also multiplicative, so we may use strong induction. Note that as all $p \geq 3$ is odd, we find that $$f(p) = f(2) + f \left(\frac{p-1}{2} \right) \geq 1 +\log_3(p-1) - log_3(2) \geq log_3 (p),$$as desired.

redacted

I tried $ n= 2^a $ , then $ n=3^b $ then $ n =2^a 3^b $ , $ n=2^a 3^b 5^c $ and then I reached to make a perfect claim...

Let $f(n)$ be the minimum number of times $\varphi$ must be applied to $n$ to reach 1. For example, $f(2)=1$. The main claim is that we can rigidly classify $f(n)$ completely in terms of $f(\text{primes})$. Key Claim: Consider the prime factorization $n=p_1^{e_1}\cdots p_k^{e_k}$ where $p_1<\cdots<p_k$. For $n\ge 2$, \[ f(n)=\begin{cases}1 + \sum_{i=1}^k \big(f(p_i)-1\big)e_i &\text{ if } 2\nmid n\\ e_1 + \sum_{i=1}^k \big(f(p_i)-1\big)e_i &\text{ if $2\mid n$, i.e. $p_1=2$}. \end{cases} \]In particular, $f(n)$ is either a linear combination of the $e_i$'s or one plus a linear combination. For example, compute manually $f(3)=2$, $f(13)=4$, and $f(37)=5$, so the claim contends that $f(3^a13^b37^c) = 1+a+3b+4c$ and $f(2^a13^b)=a+3b$. Proof: Strong induct on $n$, base cases of $n$ prime trivial. Assume that the claim holds for $1,\ldots,n-1$. For any $a,b$ with $ab \le n-1$, we can confirm from the induction hypothesis that \[f(ab)=\begin{cases}f(a) + f(b) &\text{ if } 2\mid a \text{ and } 2\mid b, \\ -1+f(a)+f(b) &\text{ if } 2\nmid a \text{ or } 2\nmid b. \end{cases} \qquad (\spadesuit)\]We have $f(n) = 1+f(\varphi(n)$ by definition. Also, in particular, $f(p)=1+f(p-1)$, so $f(p-1)=f(p)-1$ for primes $p$. Case 1: $2\nmid n$. Since $\varphi(n)<n$, we can use $(\spadesuit)$: \begin{align*} f(n) &= 1+f(\varphi(n)) \\ &= 1+f\big( (p_1-1)\cdots (p_k-1) p_1^{e_1-1}\cdots p_k^{e_k-1} \big) \\ &= 1+\left[ -1+ f(p_1-1) + \cdots + f(p_k-1) + f\big(p_1^{e_1-1}\cdots p_k^{e_k-1} \big)\right] \\ &= [f(p_1)-1] +\cdots + [f(p_k)-1] + \left[ 1 + \sum_{i=1}^k \big( f(p_i)-1\big)(e_i-1) \right] \\ &= 1 + \sum_{i=1}^k \big(f(p_i)-1\big)e_i. \end{align*}We can also confirm that even if $e_1=1$, the claimed induction still holds. Case 2: $2\mid n$. Then $p_1=2$. Since $\varphi(n)<n$, we can use $(\spadesuit)$: \begin{align*} f(n) &= 1+f(\varphi(n)) \\ &= 1+f\big( (p_1-1)\cdots (p_k-1) p_1^{e_1-1}\cdots p_k^{e_k-1} \big) \\ &= 1+\left[ f(p_1-1) + \cdots + f(p_k-1) + f\big(p_1^{e_1-1}\cdots p_k^{e_k-1} \big)\right] \\ &= 1+ [f(p_1)-1] +\cdots + [f(p_k)-1] + \left[ (e_1-1) + \sum_{i=1}^k \big( f(p_i)-1\big)(e_i-1) \right] \\ &= e_1 + \sum_{i=1}^k \big(f(p_i)-1\big)e_i. \end{align*} This finishes the induction, and proves the claim. $\blacksquare$ We claim that $f(n) \le \log_3(n)$. Since the claim holds for all $n$, we have that $(\spadesuit)$ holds for all $a$ and $b$. In particular, $f(ab) \le f(a)+f(b)$. Hence it suffices to show $f(p) \le \log_3(p)$ for primes $p$. Induct. The prime factors of $\tfrac{p-1}{2}$ are all less than $p$, so \begin{align*} f(p) &= f(p-1) + 1 \\ &= \left[-1+f(2^{\nu_2(p-1)}) + f\left(\frac{p-1}{2^{\nu_2(p-1)}}\right)\right]+1 \\ &\le \log_3(2^{\nu_2(p-1)}) + \log_3\left(\frac{p-1}{2^{\nu_2(p-1)}}\right) \\ &= \log_3(p-1) \\ &<\log_3(p), \end{align*}and we are done. Note that we had to use $(\spadesuit)$ above beyond just the weaker $f(ab)\le f(a)+f(b)$ inequality.

We actually prove the better bound $n \le 2\cdot 3^{k-1}$. Claim: For a given $k$, the upper bound of $n$ is not odd. Proof. Consider a maximal odd natural number $n$ where $\varphi^k(n) = 1$. Then $\varphi^k(2n) = 1$, contradiction to maximality. This implies that we can consider even $n$ only. Note that for even $n$, each application of the $\varphi$ function gets rid of exactly one of the 2's in the prime factorization of $n$, while odd primes contribute smaller odd primes or more 2's to the prime factorization. This implies that, for even $n$, the minimum number of iterations must be equal to the total amount of 2's produced by all of the primes over the course of the function's application. Let $f(n)$ be the total number of 2's produced by a number $n$ after repeated applications of the $\varphi$ function. Clearly, we have that $f(ab) = f(a)+f(b)$, with $f(p)=f(p-1)$ for prime $p$ and $f(2) = 1$. Note that for even $n$, the minimum number of iterations we need to apply is exactly $f(n)$. Claim: $f(n) \ge \log_3(n)$ for $n \ge 2$ Proof: We proceed by strong induction on $n$. Note that we only need to prove the result for primes $p$, then the result for composite numbers is immediate. We have the base cases $f(3) = f(2) = 1$. Then, for prime $p$, $$f(p) = f(p-1) = f\left(\frac{p-1}{2}\right) + f(2) = f\left(\frac{p-1}{2}\right) + f(3) \ge \log_3\left(\frac{p-1}{2}\right) + \log_3(3) = \log_3\left(\frac{3(p-1)}{2}\right) \ge \log_3(p)$$ Now, for maximal even $n$, with $\varphi^k(n)=1$, note that $f(n) = k$. Thus we have that \begin{align*} f(n) &\ge \log_3(n)\\ k &\ge \log_3(n)\\ k-1 &\ge \log_3(\tfrac{n}{2})\\ 3^{k-1} &\ge \tfrac{n}{2}\\ \Aboxed{2\cdot 3^{k-1} &\ge n} \end{align*}as desired.

Note that the $\phi(x)$ function decreases $v_2(x)$ by at most $1$, and only when $x$ is a power of $2$. Define $f(x)$ to be the maximal possible $v_2$ value upon repeatedly applying $\phi$ to $x$. It follows that $k \geq f(x)$, equality achieved when $x$ is a power of $2$. Now we shall prove a lower bound of $f(x)$ is $\log_3(x)$. We strong induct on $x$, based on the largest prime dividing $x$. The base cases of $x = 1$ and $x = 2^k$ are trivial, and for the inductive step, if the result holds for all $x$ for which only primes $p_i < p$ divide it, then for any $n$ with largest prime $p$ dividing it, note\[f(n) = f(p^m) + f(n/p^m) \geq mf(p-1) + \log_3(n/p^m) \geq \log_3(n)\]where $m = v_p(n)$, finishing the induction as desired.

My solution is similar to pad's solution (#20), except that I proved the best bound: $n \leq 2 \cdot 3^{k-1}$. So I'll copy it since there's no point in writing it again. Solution. pad wrote: Let $f(n)$ be the minimum number of times $\varphi$ must be applied to $n$ to reach 1. For example, $f(2)=1$. The main claim is that we can rigidly classify $f(n)$ completely in terms of $f(\text{primes})$. Key Claim: Consider the prime factorization $n=p_1^{e_1}\cdots p_k^{e_k}$ where $p_1<\cdots<p_k$. For $n\ge 2$, \[ f(n)=\begin{cases}1 + \sum_{i=1}^k \big(f(p_i)-1\big)e_i &\text{ if } 2\nmid n\\ e_1 + \sum_{i=1}^k \big(f(p_i)-1\big)e_i &\text{ if $2\mid n$, i.e. $p_1=2$}. \end{cases} \]In particular, $f(n)$ is either a linear combination of the $e_i$'s or one plus a linear combination. For example, compute manually $f(3)=2$, $f(13)=4$, and $f(37)=5$, so the claim contends that $f(3^a13^b37^c) = 1+a+3b+4c$ and $f(2^a13^b)=a+3b$. Proof: Strong induct on $n$, base cases of $n$ prime trivial. Assume that the claim holds for $1,\ldots,n-1$. For any $a,b$ with $ab \le n-1$, we can confirm from the induction hypothesis that \[f(ab)=\begin{cases}f(a) + f(b) &\text{ if } 2\mid a \text{ and } 2\mid b, \\ -1+f(a)+f(b) &\text{ if } 2\nmid a \text{ or } 2\nmid b. \end{cases} \qquad (\spadesuit)\]We have $f(n) = 1+f(\varphi(n)$ by definition. Also, in particular, $f(p)=1+f(p-1)$, so $f(p-1)=f(p)-1$ for primes $p$. Case 1: $2\nmid n$. Since $\varphi(n)<n$, we can use $(\spadesuit)$: \begin{align*} f(n) &= 1+f(\varphi(n)) \\ &= 1+f\big( (p_1-1)\cdots (p_k-1) p_1^{e_1-1}\cdots p_k^{e_k-1} \big) \\ &= 1+\left[ -1+ f(p_1-1) + \cdots + f(p_k-1) + f\big(p_1^{e_1-1}\cdots p_k^{e_k-1} \big)\right] \\ &= [f(p_1)-1] +\cdots + [f(p_k)-1] + \left[ 1 + \sum_{i=1}^k \big( f(p_i)-1\big)(e_i-1) \right] \\ &= 1 + \sum_{i=1}^k \big(f(p_i)-1\big)e_i. \end{align*}We can also confirm that even if $e_1=1$, the claimed induction still holds. Case 2: $2\mid n$. Then $p_1=2$. Since $\varphi(n)<n$, we can use $(\spadesuit)$: \begin{align*} f(n) &= 1+f(\varphi(n)) \\ &= 1+f\big( (p_1-1)\cdots (p_k-1) p_1^{e_1-1}\cdots p_k^{e_k-1} \big) \\ &= 1+\left[ f(p_1-1) + \cdots + f(p_k-1) + f\big(p_1^{e_1-1}\cdots p_k^{e_k-1} \big)\right] \\ &= 1+ [f(p_1)-1] +\cdots + [f(p_k)-1] + \left[ (e_1-1) + \sum_{i=1}^k \big( f(p_i)-1\big)(e_i-1) \right] \\ &= e_1 + \sum_{i=1}^k \big(f(p_i)-1\big)e_i. \end{align*} This finishes the induction, and proves the claim. $\blacksquare$ Note that $n \leq 2 \cdot 3^{k-1} \iff f(n)\ge \log_3 \frac{3n}{2}$. Case 1. $n = 2^2 p_1^{a_1}\dots p_m^{a_m}$. Note that $f(n) = f(2\cdot 2 p_1^{a_1}\dots p_m^{a_m}) = f(2) + f(2 p_1^{a_1}\dots p_m^{a_m}) = 1 + f(2 p_1^{a_1}\dots p_m^{a_m}) \ge \log_3 3 \cdot$$ \frac{3}{2} (2 p_1^{a_1}\dots p_m^{a_m}) = \log_3 \frac{9n}{4}$ $ \ge \log_3 \frac{3n}{2}$ Case 2. $n = 2p_1^{a_1}p_2^{a_2}\dots p_m^{a_m}$ where $4 \nmid n$ and all exponents are positive. Then, $$f(n)=f(2)+f(\frac{n}{2}) -1 = f(\frac{n}{2}) = f(p_1^{a_1}\dots p_m^{a_m})$$So $f(n) = 1 + f( \left(p_1^{a_1-1}(p_1-1)\right)\dots \left(p_m^{a_m-1}(p_m-1)\right) \ge \log_3 3 \left(\frac{3}{2}\right)^m \left(p_1^{a_1-1}(p_1-1)\right)\dots \left(p_m^{a_m-1}(p_m-1)\right)\ge \log_3 \frac{3n}{2} \iff$ $$\left(\frac{3}{2}\right)^m (p_1-1)\dots (p_m-1) \ge p_1 p_2 \dots p_m$$The last is true since $\frac{3}{2}(x-1) \ge x \iff x \ge 3$. It also tells us that equality occurs when there is only one prime, $p_1=3$. So equality occurs when $n = 2 \cdot 3^{a_1}$. Case 3. $n=p_1^{a_1}\dots p_m^{a_m}$ when $2 \nmid n$ and all exponents are positive. Same as Case 2..

The logic behind this problem is a bit finicky to sort out, but nonetheless, it's a great problem. The idea is to realize that every chain of $\phi$ applications that eventually reaches $1$ for some $n$ in $k$ applications contains some $i \leq k$ with $\phi^i(n)$ a power of two. On the other hand, because $\nu_2(\phi(n)) \geq \nu_2(n)$ when $n$ is not a power of $2$, we simply need to show that this maximal $\nu_2$ is at least $\log_3 n$. Define $f(n)$ to be this value for some positive integer $n$. Because $\phi$ is multiplicative, the function $f(n)$ is logarithmically additive (more concretely, one can just convert the prime powers into powers of two separately until all odd primes disappear), and obviously $f(2) = 1$. Furthermore, $f(p) = f(p-1)$, so now $$f(p) = f(p-1) = 1+f\left(\frac{p-1}2\right) \geq 1+\log_3(p-1) - \log_3(2) \geq \log_3 p$$for odd primes $p$. Combined with additivity this is enough to show $f(n) \geq \log_3 n$ for all $n$, as needed.

woah We need to show that starting from $n$, we need to apply $\phi$ at least $\log_3(n)$ times to reach 1. Alice likes eating berries. She has $v_2(n)$ "type 2" berries, $v_3(n)$ "type 3" berries, $v_5(n)$ "type 5" berries, and so on, she has $v_p(n)$ type $p$ berries for each prime $p$. However, for whatever reason, when Alice eats a type $p$ berry, she gains another $v_2(p-1)$ type 2 berries, $v_3(p-1)$ type 3 berries, and so on (in particular, eating a type 2 berry has no gain). On each turn, Alice will eat one berry of every type that she has. The problem statement is thus equivalent to the assertion that Alice will be able to eat for at least $\log_3(n)$ turns before running out of berries. Define the value of a type $p$ berry as the number of type 2 berries that will come out of it eventually. For example, types 2,3,5,7,11 have values of 1, 1, 2, 2, and 3. Claim: A type $p$ berry has a value of at least $\log_3(p).$ We will show this by induction. Let $s(p)$ be the value of berry $p$. This is true for $p=2,3,5,7,11$ as shown earlier. Now, note that after eating a type $p$ berry, Alice gains a bunch of berries whose product of types is $p-1.$ Let these berries be $q_1,q_2\cdots q_k$ (not necessarily distinct). Note that for all $i$, $q_i<p$. The value of the original berry is equal to the sum of the values of these berries. By our inductive hypothesis, $$s(p)=\sum_{i=1}^k s(q_i)\geq \sum_{i=1}^k \log_3(q_i)=\log_3(p-1).$$However, note that $s(p)$ is an integer, but $\log_3(p-1)$ is never an integer other than $p=2$, as that requires $p$ to be even, so this can actually be strengthened to $$s(p)\geq \log_3(p),$$which shows the claim inductively. Therefore, each berry of type $p$ will produce at least $\log_3(p)$ berries of type 2 eventually. Let Alice's original berries be $b_1,b_2\cdots b_m$. Then, $$\sum_{i=1}^m s(b_i)\geq \sum_{i=1}^m \log_3(b_i)=\log_3(\prod_{i=1}^m b_i)=\log_3(n),$$so at least $\log_3(n)$ type 2 berries are produced. This clearly implies the result as no more than one type 2 berry is consumed at each turn, so we are done.

Define $\phi^m(n)$ to be $m$ applications of $\phi$. Let $\Omega(n)$ be the number of distinct odd prime divisors of $n$. Then, let $$X=\sum_{i=0}^{k-1} \Omega(\phi^i(n))$$The key observation is that at each application of $\phi(m)$, we have $$\nu_2(\phi(m))\geq \nu_2(m)+\Omega(m)-1$$which comes from $\phi(m)=m\prod_{p\mid m}\frac{p-1}{p}$ where $2\mid p-1$ except for $p=2$ which decreases $\nu_2(\phi(m))$ by $1$. Thus, $$0=\nu_2(\phi^k(n))\geq -k+\nu_2(n)+\sum_{i=0}^{k-1} \Omega(\phi^i(n))\geq X-k$$so $X\leq k$. But then, if $a_1,a_2,\ldots, a_X$ are the odd prime factors counted in $X$ in any order, \begin{align*} n&=\frac{n}{\phi(n)}\cdot \frac{\phi(n)}{\phi^2(n)}\cdot\cdots\cdot \frac{\phi^{k-1}(n)}{\phi^k(n)}\\ &\leq 2^k \prod_{i=1}^X \frac{a_i}{a_i-1}\\ &\leq 2^k \prod_{i=1}^k \frac{3}{2} && (X\leq k)\\ &=3^k. \end{align*}as desired.

Lemma: For all positive integers $n$, $\nu_2(\varphi(n)) - \nu_2(n) \ge -1$. Proof. Note that \[ \nu_2(\varphi(n)) = \nu_2(n)+\sum_{\text{prime} \ p|n} (\nu_2(p-1)-\nu_2(p)) \ge \nu_2(n)+g(n),\] where $g(n)=-1$ if $n$ is even and $g(n)=0$ if $n$ is odd; this follows immediately from the well-known formula for $\varphi(n)$. The claim follows. $\square$ Claim: Define the function $f(n)$ by $f(ab)=f(a)+f(b)$ for all positive integers $a$ and $b$; $f(2)=1$ and $f(p)=f(p-1)$ for all primes $p$. Then $k \ge f(n)$. Proof. Induction, followed by application of the Lemma. $\square$ Claim: For all positive integers $n$, $f(n) \ge \log_3(n)$. Proof. We use strong induction, where the base cases $n=1, 2$ is easy. By the logarithmic nature of $f$, it suffices to prove $f(p) \ge \log_3(p)$ for prime $p$ as the inductive step. We have \[ f(p) = f\left(\frac{p-1}{2}\right)+f(2)= f\left(\frac{p-1}{2}\right)+1 \ge \log_3(p-1)-\log_3(2)+1 = \log_3(p-1) + \log\left(\frac{3}{2}\right) \ge \log_3(p-1)+\log\left(\frac{p}{p-1}\right)=\log_3(p), \]completing the proof. $\square$ By the above two claims, $k \ge \log_3(n)$, or $n \le 3^k$, and we are done.

Incredibly long solution i got lol Solved through the walkthrough of OTIS Excerpts. Let w(ab)=w(a)+w(b), w(p)=w(p-1), and w(2)=1, with p a prime and w a function defined from natural inputs to integer outputs. Essentially, if i*2^j=n=ab even, where i is odd, obviously w(n)=w(i)+j, counting the original powers of two (which are already produced). Now for odd $n=p_1^{e_1}...p_k^{e_k}$, $$w(n)=e_1w(p_1-1)+...+e_kw(p_k-1).$$ Now the critical thing to see is that this represents the powers of two produced as phi is applied. This is because if we assume that this holds for base cases p-1, which makes the descent until the obvious p=2 and 3, $e_lw(p_l)=e_lw(p_l-1)$, which it's obvious that phi(n) also gets rid of p_l and replaces with p_l-1 every application as well. This makes the descent of replacing larger numbers with smaller, retaining the property of applications of phi(n), until we get to only w(2)s, which are just the number of powers of 2. $\square$ Obviously k is the number of phi(n) applications from when n has odd factors plus the applications when n has only powers of 2, hence k is at least w(n). So if we prove the needed inequality holds for primes, it will obviously hold for composites (since $w(n)=e_1w(p_1)+...\ge log_{3}{p_1^{e_1}}+...=log_{3}{n}$). Then by strong induction (and these inductive hypotheses will descent down until p=2 and 3, where it is trivial that it holds (w(3)=1=log_3{3})), we have that $$w(p)=w(2)+w(\frac{p-1}{2})\ge log_3{3}+log_3{\frac{p-1}{2}}=log_3{\frac{3(p-1)}{2}}\ge log_3{p},$$as desired. $\blacksquare$

That's a great number theory problem and I hope we will face a lot of beatiful NT problems like this one in the future! Let's say $n=2^k*p_1^{\alpha_1}*\ldots$, then $\phi(n)=2^{k-1}p_1^{\alpha_1-1}(p_1-1)\ldots$. If $k \geq 1$, we say that a power of two destroyed a two(if $k=0$ then nothing was destroyed), and $p_i$ has built $v_2(p_i-1)$ twos. Now here comes the key claim: Key claim In the process of applying $\phi$ function to $n$ untill the results becomes $1$ at least $log_3(n)$ twos will be built, including $v_2(n)$ initial twos. Proof: we proceed with induction on $n$. Base: $n=1$ is obvious. Induction step: first, consider even $n$. Let $k=v_2(n)$, $n=2^kX$. Then by induction in the process of $X$ at least $log_3(X)$ two will be built. We have $k$ initial so at least $k+log_3(X)=log_3(X*3^k)>log_3(n)$ will be built. Now, suppose $n$ is odd. Then $n=p_1^{a_1}*\ldots*p_k^{a_k}$. Suppose $k>1$. Then by induction at least $log_3(p_1^{a_1})+\ldots+log_3(p_k^{a_k})=log_3(n)$ twos will be produced. Now $k=1$. If $a_1>1$, then by induction at least $a_1log_3(p_1)=log_3(n)$ twos will be produced. Now $n=p$ - prime. Then $\phi(n)=p-1$. If $p=2,3$ we can manually check that everything works. Otherwise, $\lceil log_3(p) \rceil=\lceil log_3(p-1) \rceil$ (cause none of this two can be a power of three), hence we are done. Now let's finish. Note that every step destroys at most one two, thus during the whole process at most $k$ twos were destroyed. At least $log_3(n)$ were built, thus $n \leq 3^k$