%I M0244
%S 0,1,2,2,3,2,3,3,3,3,4,3,4,3,4,4,5,3,4,4,4,4,5,4,5,4,4,4,5,4,5,5,5,5,
%T 5,4,5,4,5,5,6,4,5,5,5,5,6,5,5,5,6,5,6,4,6,5,5,5,6,5,6,5,5,6,6,5,6,6,
%U 6,5,6,5,6,5,6,5,6,5,6,6,5,6,7,5,7,5,6,6,7,5,6,6,6,6,6,6,7,5,6,6,7,6,7,6,6
%N Number of iterations of phi(x) at n needed to reach 1.
%D I. Niven, The iteration of arithmetic functions, Canad. J. Math. 2 (1950), pp. 406408.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D S. Sivasankaranarayana Pillai, On a function associated with phi(n), Bull. Amer. Math. Soc., 35 (1929), 837841.
%D H. N. Shapiro, On the iterates of a certain class of arithmetic functions, Comm. Pure Appl. Math. 3 (1950), pp. 259272.
%D M. V. Subbarao, On a function connected with phi(n), J. Madras Univ. B. 27 (1957), pp. 327333.
%H T. D. Noe, <a href="/A003434/b003434.txt">Table of n, a(n) for n = 1..10000</a>
%F a(n) = A049108(n)  1.
%F By the definition of a(n) we have for n >= 2 the recursion a(n) = a(phi(n)) + 1.  Ahmed Fares (ahmedfares(AT)mydeja.com), Apr 20 2001
%F Pillai proved that log(n/2)/log(3) + 1 <= a(n) <= log(n)/log(2) + 1. [_Charles R Greathouse IV_, Mar 22, 2012]
%e If n=164 the trajectory is {164,80,32,16,8,4,2,1}. Its length is 8, thus a(164)=7.
%t f[n_] := Length@ NestWhileList[ EulerPhi, n, # != 1 &]  1; Array[f, 105] (* _Robert G. Wilson v_, Feb 07 2012 *)
%o (PARI) A003434(n)=for(k=0,n, n>1  return(k);n=eulerphi(n)) /* Works because the loop limits are evaluated only once. Using while(...) takes 50% more time. */ /* _M. F. Hasler_, Jul 01 2009 */
%o (Haskell)
%o a003434 n = fst $ until ((== 1) . snd)
%o (\(i, x) > (i + 1, a000010 x)) (0, n)
%o  _Reinhard Zumkeller_, Feb 08 2013, Jul 03 2011
%Y Cf. A000010, A007755.
%K nonn,easy,nice,look,changed
%O 1,3
%A _N. J. A. Sloane_.
