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
Keywords
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]
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
Comments