%I M0244 #82 Feb 28 2022 12:19:51

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

%C Each number n>1 occurs for the first time at the position A007755(n+1) and for the last time at 2*3^(n-1). - _Ivan Neretin_, Mar 24 2015

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D M. V. Subbarao, On a function connected with phi(n), J. Madras Univ. B. 27 (1957), pp. 327-333.

%H T. D. Noe, <a href="/A003434/b003434.txt">Table of n, a(n) for n = 1..10000</a>

%H Hartosh Singh Bal, Gaurav Bhatnagar, <a href="https://arxiv.org/abs/1903.09619">Prime number conjectures from the Shapiro class structure</a>, arXiv:1903.09619 [math.NT], 2019.

%H C. Defant, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Defant/defant5.html">On Arithmetic Functions Related to Iterates of the Schemmel Totient Functions</a>, J. Int. Seq. 18 (2015) # 15.2.1.

%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 Erdős, 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 I. Niven, <a href="http://dx.doi.org/10.4153/CJM-1950-037-0">The iteration of certain arithmetic functions</a>, Canad. J. Math. 2 (1950), pp. 406-408.

%H H. N. Shapiro, <a href="http://dx.doi.org/10.1002/cpa.3160030304">On the iterates of a certain class of arithmetic functions</a>, Comm. Pure Appl. Math. 3 (1950), pp. 259-272.

%H S. Sivasankaranarayana Pillai, <a href="http://projecteuclid.org/euclid.bams/1183493597">On a function connected with phi(n)</a>, Bull. Amer. Math. Soc., 35:6 (1929), pp. 837-841.

%H S. Sivasankaranarayana Pillai, <a href="/A003434/a003434.pdf">On a function connected with phi(n)</a>, Bull. Amer. Math. Soc., 35.6 (1929), 837-841. (Annotated scanned copy)

%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)my-deja.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.

%p A003434 := proc(n)

%p local a, e;

%p e := n ;

%p a :=0 ;

%p while e > 1 do

%p a := a+1 ;

%p e := numtheory[phi](e) ;

%p end do:

%p a;

%p end proc:

%p seq(A003434(n),n=1..40) ; # _R. J. Mathar_, Jan 09 2017

%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

%o (Python)

%o from sympy import totient

%o def A003434(n):

%o c, m = 0, n

%o while m > 1:

%o c += 1

%o m = totient(m)

%o return c # _Chai Wah Wu_, Nov 14 2021

%Y Cf. A000010, A007755.

%K nonn,easy,nice,look

%O 1,3

%A _N. J. A. Sloane_