cp's OEIS Frontend

A032358 Number of iterations of phi(n) needed to reach 2.

%I A032358 #48 Sep 02 2017 14:26:09
%S A032358 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 A032358 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 A032358 4,5,4,5,4,5,4,5,4,5,5
%N A032358 Number of iterations of phi(n) needed to reach 2.
%C A032358 This sequence is additive (but not completely additive). [_Charles R Greathouse IV_, Oct 28 2011]
%C A032358 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 A032358 This is A003434(n)-1 for n>1. - _N. J. A. Sloane_, Sep 02 2017
%H A032358 Reinhard Zumkeller, <a href="/A032358/b032358.txt">Table of n, a(n) for n = 2..10000</a>
%H A032358 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 A032358 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 A032358 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 A032358 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 A032358 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 A032358 a(n) = a(phi(n))+1, a(1) = -1. - _Vladeta Jovovic_, Apr 29 2003
%F A032358 a(n) = A003434(n) - 1 = A049108(n) - 2.
%F A032358 From _Charles R Greathouse IV_, Oct 28 2011:  (Start)
%F A032358 Shapiro proves that log_3(n/2) <= a(n) < log_2(n) and also
%F A032358 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 A032358 (End)
%p A032358 A032358 := proc(n)
%p A032358     local a,phin ;
%p A032358     if n <=2 then
%p A032358         0;
%p A032358     else
%p A032358         phin := n ;
%p A032358         a := 0 ;
%p A032358         for a from 1 do
%p A032358             phin := numtheory[phi](phin) ;
%p A032358             if phin = 2 then
%p A032358                 return a;
%p A032358             end if;
%p A032358         end do:
%p A032358     end if;
%p A032358 end proc:
%p A032358 seq(A032358(n),n=1..30) ; # _R. J. Mathar_, Aug 28 2015
%t A032358 Table[Length[NestWhileList[EulerPhi[#]&,n,#>2&]]-1,{n,3,80}] (* _Harvey P. Dale_, May 01 2011 *)
%o A032358 (Haskell)
%o A032358 a032358 = length . takeWhile (/= 2) . (iterate a000010)
%o A032358 -- _Reinhard Zumkeller_, Oct 27 2011
%o A032358 (PARI) a(n)=my(t);while(n>2,n=eulerphi(n);t++);t \\ _Charles R Greathouse IV_, Oct 28 2011
%Y A032358 Cf. A000010, A003434.
%K A032358 nice,nonn,easy
%O A032358 2,4
%A A032358 Ursula Gagelmann (gagelmann(AT)altavista.net)
%E A032358 a(2) = 0 added and offset adjusted, suggested by _David W. Wilson_