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

%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_