A053044 - OEIS

%I #32 Aug 13 2024 04:04:36

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

%T 74,77,81,85,89,93,98,102,107,111,115,119,123,127,132,137,141,145,150,

%U 154,159,164,169,173,178,183,188,193,197,202,207,211,216,221,226,231

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

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

%C Partial sums of A064415.

%H Amiram Eldar, <a href="/A053044/b053044.txt">Table of n, a(n) for n = 1..10000</a>

%H Paul Erdős, Andrew Granville, Carl Pomerance and Claudia Spiro, <a href="http://math.dartmouth.edu/~carlp/iterate.pdf">On the normal behavior of the iterates of some arithmetic functions</a>, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204.

%H Paul Erdos, Andrew Granville, Carl Pomerance and Claudia Spiro, <a href="/A000010/a000010_1.pdf">On the normal behavior of the iterates of some arithmetic functions</a>, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204. [Annotated copy with A-numbers]

%F a(n) = A003434(A000142(n)). - _Michel Marcus_, Jan 01 2017

%e For n=1, no iteration is needed, so a(1)=0;

%e for n=2, the initial value is 2! = 2, so phi() must be applied once, thus a(2)=1;

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

%t Table[Length@ NestWhileList[EulerPhi, n!, # > 1 &] - 1, {n, 61}] (* or *)

%t Table[Length@ FixedPointList[EulerPhi, n!] - 2, {n, 61}] (* _Michael De Vlieger_, Jan 01 2017 *)

%o (PARI) a(n) = {my(nb = 0, ns = n!); while (ns != 1, ns = eulerphi(ns); nb++); nb;} \\ _Michel Marcus_, Jan 01 2017

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

%Y Cf. also A064415.

%K nonn

%O 1,3

%A _Labos Elemer_, Feb 25 2000