%I #48 Sep 02 2017 14:26:09
%S 0,1,1,2,1,2,2,2,2,3,2,3,2,3,3,4,2,3,3,3,3,4,3,4,3,3,3,4,3,4,4,4,4,4,
%T 3,4,3,4,4,5,3,4,4,4,4,5,4,4,4,5,4,5,3,5,4,4,4,5,4,5,4,4,5,5,4,5,5,5,
%U 4,5,4,5,4,5,4,5,4,5,5
%N Number of iterations of phi(n) needed to reach 2.
%C This sequence is additive (but not completely additive). [_Charles R Greathouse IV_, Oct 28 2011]
%C Shapiro asks for a proof that for every n > 1 there is a prime p such that a(p) = n. [_Charles R Greathouse IV_, Oct 28 2011]
%C This is A003434(n)-1 for n>1. - _N. J. A. Sloane_, Sep 02 2017
%H Reinhard Zumkeller, <a href="/A032358/b032358.txt">Table of n, a(n) for n = 2..10000</a>
%H P. A. Catlin, <a href="http://www.jstor.org/stable/2316857">Concerning the iterated phi-function</a>, Amer Math. Monthly 77 (1970), pp. 60-61.
%H Paul Erdős, Andrew Granville, Carl Pomerance and Claudia Spiro, <a href="http://math.dartmouth.edu/~carlp/iterate.pdf">On the normal behavior of the iterates of some arithmetic functions</a>, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204.
%H Paul Erdos, Andrew Granville, Carl Pomerance and Claudia Spiro, <a href="/A000010/a000010_1.pdf">On the normal behavior of the iterates of some arithmetic functions</a>, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204. [Annotated copy with A-numbers]
%H T. D. Noe, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL11/Noe/noe080107.html">Primes in classes of the iterated totient function</a>, JIS 11 (2008) 08.1.2, sequence C(x).
%H Harold Shapiro, <a href="http://www.jstor.org/stable/2303988">An arithmetic function arising from the phi function</a>, Amer. Math. Monthly, Vol. 50, No. 1 (1943), 18-30.
%F a(n) = a(phi(n))+1, a(1) = -1. - _Vladeta Jovovic_, Apr 29 2003
%F a(n) = A003434(n) - 1 = A049108(n) - 2.
%F From _Charles R Greathouse IV_, Oct 28 2011: (Start)
%F Shapiro proves that log_3(n/2) <= a(n) < log_2(n) and also
%F a(mn) = a(m) + a(n) if either m or n is odd and a(mn) = a(m) + a(n) + 1 if m and n are even.
%F (End)
%p A032358 := proc(n)
%p local a,phin ;
%p if n <=2 then
%p 0;
%p else
%p phin := n ;
%p a := 0 ;
%p for a from 1 do
%p phin := numtheory[phi](phin) ;
%p if phin = 2 then
%p return a;
%p end if;
%p end do:
%p end if;
%p end proc:
%p seq(A032358(n),n=1..30) ; # _R. J. Mathar_, Aug 28 2015
%t Table[Length[NestWhileList[EulerPhi[#]&,n,#>2&]]-1,{n,3,80}] (* _Harvey P. Dale_, May 01 2011 *)
%o (Haskell)
%o a032358 = length . takeWhile (/= 2) . (iterate a000010)
%o -- _Reinhard Zumkeller_, Oct 27 2011
%o (PARI) a(n)=my(t);while(n>2,n=eulerphi(n);t++);t \\ _Charles R Greathouse IV_, Oct 28 2011
%Y Cf. A000010, A003434.
%K nice,nonn,easy
%O 2,4
%A Ursula Gagelmann (gagelmann(AT)altavista.net)
%E a(2) = 0 added and offset adjusted, suggested by _David W. Wilson_