cp's OEIS Frontend

A003434 Number of iterations of phi(x) at n needed to reach 1.

%I A003434 M0244 #82 Feb 28 2022 12:19:51
%S A003434 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 A003434 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 A003434 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 A003434 Number of iterations of phi(x) at n needed to reach 1.
%C A003434 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 A003434 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A003434 M. V. Subbarao, On a function connected with phi(n), J. Madras Univ. B. 27 (1957), pp. 327-333.
%H A003434 T. D. Noe, <a href="/A003434/b003434.txt">Table of n, a(n) for n = 1..10000</a>
%H A003434 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 A003434 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 A003434 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 A003434 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 A003434 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 A003434 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 A003434 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 A003434 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 A003434 a(n) = A049108(n) - 1.
%F A003434 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 A003434 Pillai proved that log(n/2)/log(3) + 1 <= a(n) <= log(n)/log(2) + 1. - _Charles R Greathouse IV_, Mar 22 2012
%e A003434 If n=164 the trajectory is {164,80,32,16,8,4,2,1}. Its length is 8, thus a(164)=7.
%p A003434 A003434 := proc(n)
%p A003434     local a, e;
%p A003434     e := n ;
%p A003434     a :=0 ;
%p A003434     while e > 1 do
%p A003434         a := a+1 ;
%p A003434         e := numtheory[phi](e) ;
%p A003434     end do:
%p A003434     a;
%p A003434 end proc:
%p A003434 seq(A003434(n),n=1..40) ; # _R. J. Mathar_, Jan 09 2017
%t A003434 f[n_] := Length@ NestWhileList[ EulerPhi, n, # != 1 &] - 1; Array[f, 105] (* _Robert G. Wilson v_, Feb 07 2012 *)
%o A003434 (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 A003434 (Haskell)
%o A003434 a003434 n = fst $ until ((== 1) . snd)
%o A003434                         (\(i, x) -> (i + 1, a000010 x)) (0, n)
%o A003434 -- _Reinhard Zumkeller_, Feb 08 2013, Jul 03 2011
%o A003434 (Python)
%o A003434 from sympy import totient
%o A003434 def A003434(n):
%o A003434     c, m = 0, n
%o A003434     while m > 1:
%o A003434         c += 1
%o A003434         m = totient(m)
%o A003434     return c # _Chai Wah Wu_, Nov 14 2021
%Y A003434 Cf. A000010, A007755.
%K A003434 nonn,easy,nice,look
%O A003434 1,3
%A A003434 _N. J. A. Sloane_