cp's OEIS Frontend

A362024 The number of iterations of the infinitary totient function iphi (A064380) required to reach from n to 1.

%I A362024 #11 Apr 09 2023 02:01:54
%S A362024 1,2,3,4,3,4,4,5,5,6,5,6,5,6,7,8,7,8,7,6,6,7,6,7,8,8,9,10,7,8,8,7,7,8,
%T A362024 9,10,7,9,8,9,9,10,9,8,11,12,8,9,9,10,10,11,7,10,9,9,11,12,8,9,9,10,9,
%U A362024 10,8,9,11,10,9,10,8,9,9,8,10,10,10,11,11,12
%N A362024 The number of iterations of the infinitary totient function iphi (A064380) required to reach from n to 1.
%H A362024 Amiram Eldar, <a href="/A362024/b362024.txt">Table of n, a(n) for n = 2..10000</a>
%F A362024 a(n) = a(A064380(n)) + 1 for n > 2.
%e A362024 a(6) = 3 since there are 3 iterations from 6 to 1: iphi(6) = 3, iphi(3) = 2 and iphi(2) = 1.
%t A362024 infCoprimeQ[n1_, n2_] := Module[{g = GCD[n1, n2]}, If[g == 1, True, AllTrue[FactorInteger[g][[;; , 1]], BitAnd @@ IntegerExponent[{n1, n2}, #] == 0 &]]];
%t A362024 iphi[n_] := Sum[Boole[infCoprimeQ[j, n]], {j, 1, n - 1}];
%t A362024 a[n_] := Length@ NestWhileList[iphi, n, # > 1 &] - 1;
%t A362024 Array[a, 100, 2]
%o A362024 (PARI) isinfcoprime(n1, n2) = {my(g = gcd(n1, n2), p, e1, e2); if(g == 1, return(1)); p = factor(g)[, 1]; for(i=1, #p, e1 = valuation(n1, p[i]); e2 = valuation(n2, p[i]); if(bitand(e1, e2) > 0, return(0))); 1; }
%o A362024 iphi(n) = sum(j = 1, n-1, isinfcoprime(j, n));
%o A362024 a(n) = if(n==2, 1, a(iphi(n)) + 1);
%Y A362024 Cf. A064380, A362025 (indices of records).
%Y A362024 Similar sequences: A003434, A049865, A333609.
%K A362024 nonn
%O A362024 2,2
%A A362024 _Amiram Eldar_, Apr 05 2023