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,3

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.

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]

Formula

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

Example

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.

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 *)

Prog

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

Crossrefs

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

Cf. also A064415.

Sequence in context: A332687 A345981 A371186 * A129011 A130174 A061168

Adjacent sequences: A053041 A053042 A053043 * A053045 A053046 A053047

Keyword

nonn

Author

Labos Elemer, Feb 25 2000

Status

approved