1,2

Least integer k such that the number of iterations of Euler phi function needed to reach 1 starting at k (k is counted) is n.

a(n) is smallest number in the class k(n) which groups families of integers which take the same number of iterations of the totient function to evolve to 1. The maximum is 2*3^(n-1).

Shapiro shows that the smallest number is greater the 2^(n-1). Catlin shows that if a(n) is odd and composite, then its factors are among the a(k), k < n. For example a(12) = a(5) a(8). There is a conjecture that all terms of this sequence are odd. - T. D. Noe (noe(AT)sspectra.com), Mar 08 2004

The indices of odd prime terms are given by n=A136040(k)+2 for k=1,2,3,.... - T. D. Noe, Dec 14 2007

P. A. Catlin, Concerning the iterated phi function, Amer. Math. Monthly, Vol. 77, No. 1 (1970), 60-61.

J.-M. De Koninck, Ces nombres qui nous fascinent, Entry 83, p. 29, Ellipses, Paris 2008. Also Entry 137, p. 47.

R. K. Guy, Unsolved Problems in Number Theory, 2nd Ed. New York: Springer-Verlag, p. 97, 1994, Section B41.

Harold Shapiro, An arithmetic function arising from the phi function, Amer. Math. Monthly, Vol. 50, No. 1 (1943), 18-30.

T. D. Noe, Table of n, a(n) for n=1..1002

T. D. Noe, Computing Numbers in Section I of the Totient Iteration [From T. D. Noe (noe(AT)sspectra.com), Nov 18 2008]

a(n+2) ~ 2^n.

n=3, a[3]=3 because trajectory={3,2,1}. n=1: a[1]=1 because trajectory={1}

f[n_] := Length[ NestWhileList[ EulerPhi, n, Unequal, 2]] - 1; a = Table[0, {30}]; Do[b = f[n]; If[a[[b]] == 0, a[[b]] = n; Print[n, " = ", b]], {n, 1, 22500000}] (from Robert G. Wilson v)

Cf. A000010, A003434, A049108, A092873 (prime factors of a(n)), A060611, A098196.

Sequence in context: A062737 A085613 A082605 this_sequence A060611 A103598 A077497

Adjacent sequences: A007752 A007753 A007754 this_sequence A007756 A007757 A007758

nonn

Pepijn van Erp [ vanerp(AT)sci.kun.nl ]

More terms from David W. Wilson (davidwwilson(AT)comcast.net) May 15 1997

Additional comments from James S. Cronen (cronej(AT)rpi.edu)