login
This site is supported by donations to The OEIS Foundation.

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003434 Number of iterations of phi(x) at n needed to reach 1.
(Formerly M0244)
24

%I M0244

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

%D I. Niven, The iteration of arithmetic functions, Canad. J. Math. 2 (1950), pp. 406-408.

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

%D S. Sivasankaranarayana Pillai, On a function associated with phi(n), Bull. Amer. Math. Soc., 35 (1929), 837-841.

%D H. N. Shapiro, On the iterates of a certain class of arithmetic functions, Comm. Pure Appl. Math. 3 (1950), pp. 259-272.

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

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

%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

%Y Cf. A000010, A007755.

%K nonn,easy,nice,look

%O 1,3

%A _N. J. A. Sloane_.

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified September 1 10:09 EDT 2014. Contains 246291 sequences.