MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 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.

share|cite|improve this question
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
up vote 9 down vote accepted

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}]$.

"On a function connected with ϕ(n)" S. S. Pillai, Bull. Amer. Math. Soc. Volume 35, Number 6 (1929), 837-841.

share|cite|improve this answer
The paper: – J. M. Nov 22 '11 at 4:37

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.