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$?


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


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .