A053044 a(n) is the number of iterations of the Euler totient function to reach 1, starting at n!.

0, 1, 2, 4, 6, 8, 10, 13, 15, 18, 21, 24, 27, 30, 33, 37, 41, 44, 47, 51, 54, 58, 62, 66, 70, 74, 77, 81, 85, 89, 93, 98, 102, 107, 111, 115, 119, 123, 127, 132, 137, 141, 145, 150, 154, 159, 164, 169, 173, 178, 183, 188, 193, 197, 202, 207, 211, 216, 221, 226, 231

Offset: 1

Author

Labos Elemer, Feb 25 2000

Keywords

• nonn

Comments

Powers of 2 arise at the end of iteration chains without interruption. Analogous to A053025 and A053034. The order of speed of convergence is as follows: A000005 > A000010 > A051953: e.g., for 20! the lengths of the corresponding iteration chains are 6, 51, and 101, respectively.

Partial sums of A064415.

Examples

			For n=1, no iteration is needed, so a(1)=0;
for n=2, the initial value is 2! = 2, so phi() must be applied once, thus a(2)=1;
for n=8, the iteration chain is {40320, 9216, 3072, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1}; its length = 14 = a(8) + 1, so the number of iterations applied to reach 1 is a(8)=13.
		

Links

• Amiram Eldar, Table of n, a(n) for n = 1..10000
• Paul Erdős, Andrew Granville, Carl Pomerance and Claudia Spiro, On the normal behavior of the iterates of some arithmetic functions, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204.
• Paul Erdos, Andrew Granville, Carl Pomerance and Claudia Spiro, On the normal behavior of the iterates of some arithmetic functions, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204. [Annotated copy with A-numbers]

Crossrefs

Cf. A000010, A000142, A003434, A053025, A053034.

Cf. also A064415.

Programs

Mathematica

Table[Length@ NestWhileList[EulerPhi, n!, # > 1 &] - 1, {n, 61}] (* or *)
Table[Length@ FixedPointList[EulerPhi, n!] - 2, {n, 61}] (* Michael De Vlieger, Jan 01 2017 *)

PARI

a(n) = {my(nb = 0, ns = n!); while (ns != 1, ns = eulerphi(ns); nb++); nb;} \\ Michel Marcus, Jan 01 2017

Formula

a(n) = A003434(A000142(n)). - Michel Marcus, Jan 01 2017