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