Please bare my wordings, I am not good at English nor Maths.

Let $\phi(N)$ be Euler's totient function, I would like to know how can one find out how many $k$ consecutive $\phi$ on $N$ to make it converage to $1$? $i.e$

$$\phi(\phi(\phi(...\phi(N)))$$ where there is $k$ $\phi$ there.

From wiki, it seems that it drops to 1 very fast (needs $k = 6$):

$\phi(\phi(\phi(\phi(\phi(\phi(99))))))$ = 1

So I wonder, is there any known order bound like $k = O(lg N)$ for $k$ $\phi$ on $N$ to get $1$?


This sequence is on OEIS at https://oeis.org/A003434.

It is indeed known that $k \le \frac{\log(N)}{\log(2)} + 1.$ This is proved here.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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