# Repetitions of the totient

In a program I'm writing I'm using that the function:

$rphi(1) = 0$

$rphi(n) = 1+rphi(phi(n))$

grows very slowly. Judging from https://oeis.org/A003434 it would seam like it is approximately logarithmic.

I was wondering if there are any known bounds on this function? Oeis didn't mention any.

-
well, $rphi(2^k)= k$, so it is logarithmic on powers of $2$ at least. – Timothy Foo Nov 22 '11 at 0:11
$\varphi(n)$ is even for all $n$ and $\varphi(n)\le n/2$ for even $n$, which means that your recursion reaches the base case $1$ in at most $1+\log_2 n$ steps. The clean logarithmic lower bound may be a bit harder Do you care if it is $\log n$ or $\log n/\log\log n$? – fedja Nov 22 '11 at 0:16

This is a result of Pillai. Indeed we have $\text{rphi}(n)=\frac{\log n}{\log 2}$ when $n$ is a power of 2, and we have $\text{rphi}(n)=\lceil\frac{\log n}{\log 3}\rceil$ when $n$ is twice a power of 3. Pillai proved that these two cases characterise the extremal behaviour of $\text{rphi(n})$.
$$\lceil\frac{\log n}{\log 2}\rceil\geq\text{rphi}(n)\geq\lceil\frac{\log n}{\log 3}\rceil$$ If one considers the numbers $n=2^a3^b$ one can see that $\frac{\text{rphi}(n)}{\log n}$ is dense in $[\frac{1}{\log 3},\frac{1}{\log 2}]$.