A073407 Let phi_m(x) denote the Euler totient function applied m times to x. Sequence gives the minimum number of iterations m such that phi_m(n) divides n.
1, 1, 2, 1, 3, 1, 3, 1, 3, 2, 4, 1, 4, 2, 4, 1, 5, 1, 4, 2, 4, 3, 5, 1, 5, 3, 4, 2, 5, 3, 5, 1, 5, 4, 5, 1, 5, 3, 5, 2, 6, 3, 5, 3, 5, 4, 6, 1, 5, 4, 6, 3, 6, 1, 6, 2, 5, 4, 6, 3, 6, 4, 5, 1, 6, 4, 6, 4, 6, 4, 6, 1, 6, 4, 6, 3, 6, 4, 6, 2, 5, 5, 7, 3, 7, 4, 6, 3, 7, 4, 6, 4, 6, 5, 6, 1, 7, 4, 6, 4, 7, 5, 7, 3, 6
Offset: 1
Examples
phi(22) -> 10, phi(10) -> 4, phi(4) -> 2 and 2 divides 22. Hence 3 iterations are needed and a(22) = 3.
Links
- Amiram Eldar, Table of n, a(n) for n = 1..10000
Programs
-
Mathematica
a[n_] := Module[{c = 0, k = n}, While[c == 0 || !Divisible[n, k], k = EulerPhi[k]; c++]; c]; Array[a, 105] (* Amiram Eldar, Jul 10 2019 *) -
PARI
a(n) = if(n<0,0,c=1; s=n; while(n%eulerphi(s)>0,s=eulerphi(s); c++); c)
Formula
It seems that sum(k=1, n, a(k)) is asymptotic to C*n*log(n) with C>1.