Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
1  
well, $rphi(2^k)= k$, so it is logarithmic on powers of $2$ at least. –  Timothy Foo Nov 22 '11 at 0:11
1  
$\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

1 Answer 1

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|improve this answer
    
The paper: dx.doi.org/10.1090/S0002-9904-1929-04800-6 –  J. M. Nov 22 '11 at 4:37

Your Answer

 
discard

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.