About Euler totient function $\underbrace{\varphi( \varphi( \dots \varphi(}_{k\ \text{times}} n) \dots ))$

Question

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$). How can I show that $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.

Answer 1

It will be convenient for stating results to define $f(1)=0$.

Let $n$ be minimal such that $n$ can be expressed as a product which is a counterexample to this result. We shall first prove a couple of Lemmas.

Let $PQ\le n$, where $P$ and $Q$ are coprime. Then $f(PQ)=f(P)+f(Q)$.

Proof

$\phi(PQ)=\phi(P)\phi(Q)$ and so $f(PQ)=1+f\left (\phi(P)\phi(Q)\right)$, where $\phi(P)\phi(Q)<n$.

If either $P$ or $Q$ is $1$ or $2$, then the result is trivial so we can suppose that both $\phi(P)\text { and }\phi(Q)$ are even.

Then $f(PQ)=1+f (\phi(P))+f(\phi(Q))+1=f(P)+f(Q)$.

If $a\ge1, f(2^a)=a-1$ and, if $p$ is an odd prime such that $2^a\le n$, then $f(p^a)=af(p).$

Proof

Since $\phi(2^a)=2^{a-1}$ we have $f(2^a)=a-1$.

Since $\phi(p^a)=p^{a-1}(p-1)$ we have $$f(p^a)=1+f\left (p^{a-1}(p-1)\right )=1+f\left (p^{a-1}\right)+f\left (p-1\right )=f\left (p^{a-1}\right)+f(p).$$ Therefore $f(p^a)=af(p).$

Solution

Let $n=uv$ and let a prime $p$ occur to power $a$ in $u$ and to power $b$ in $v$.

If $p$ is odd, this prime contributes the same amount, $(a+b)(p-1)$, to both$f(uv)$ and $f(u)+f(v)$.

If $p=2$ and occurs in only one of $u$ and $v$ then it also contributes the same to $f(uv)$ and $f(u)+f(v)$. Therefore $f(uv)=f(u)+f(v)$.

If $p=2$ and if $ab>0$, then it contributes $a+b-1$ to $f(uv)$ and $a-1+b-1$ to $f(u)+f(v)$. Therefore $f(uv)=f(u)+f(v)+1$.