cp's OEIS Frontend

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

%I A053044 #32 Aug 13 2024 04:04:36
%S A053044 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 A053044 74,77,81,85,89,93,98,102,107,111,115,119,123,127,132,137,141,145,150,
%U A053044 154,159,164,169,173,178,183,188,193,197,202,207,211,216,221,226,231
%N A053044 a(n) is the number of iterations of the Euler totient function to reach 1, starting at n!.
%C A053044 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 A053044 Partial sums of A064415.
%H A053044 Amiram Eldar, <a href="/A053044/b053044.txt">Table of n, a(n) for n = 1..10000</a>
%H A053044 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 A053044 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 A053044 a(n) = A003434(A000142(n)). - _Michel Marcus_, Jan 01 2017
%e A053044 For n=1, no iteration is needed, so a(1)=0;
%e A053044 for n=2, the initial value is 2! = 2, so phi() must be applied once, thus a(2)=1;
%e A053044 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 A053044 Table[Length@ NestWhileList[EulerPhi, n!, # > 1 &] - 1, {n, 61}] (* or *)
%t A053044 Table[Length@ FixedPointList[EulerPhi, n!] - 2, {n, 61}] (* _Michael De Vlieger_, Jan 01 2017 *)
%o A053044 (PARI) a(n) = {my(nb = 0, ns = n!); while (ns != 1, ns = eulerphi(ns); nb++); nb;} \\ _Michel Marcus_, Jan 01 2017
%Y A053044 Cf. A000010, A000142, A003434, A053025, A053034.
%Y A053044 Cf. also A064415.
%K A053044 nonn
%O A053044 1,3
%A A053044 _Labos Elemer_, Feb 25 2000