cp's OEIS Frontend

A023138 Number of cycles of function f(x) = 6x mod n.

%I A023138 #27 Apr 10 2024 03:30:28
%S A023138 1,1,1,1,5,1,4,1,1,5,2,1,2,4,5,1,2,1,3,5,4,2,3,1,9,2,1,4,3,5,6,1,2,2,
%T A023138 20,1,10,3,2,5,2,4,15,2,5,3,3,1,7,9,2,2,3,1,10,4,3,3,2,5,2,6,4,1,10,2,
%U A023138 3,2,3,20,3,1,3,10,9,3,11,2,2,5,1,2,2,4,10,15,3,2,2,5,11,3,6,3,15,1,9,7,2,9,11
%N A023138 Number of cycles of function f(x) = 6x mod n.
%H A023138 T. D. Noe, <a href="/A023138/b023138.txt">Table of n, a(n) for n = 1..10000</a>
%F A023138 a(n) = Sum_{d|m} phi(d)/ord(6, d), where m is n with all factors of 2 and 3 removed. - _T. D. Noe_, Apr 21 2003
%F A023138 a(n) = (1/ord(6,m))*Sum_{j = 0..ord(6,m)-1} gcd(6^j - 1, m), where m is n with all factors of 2 and 3 removed. - _Nihar Prakash Gargava_, Nov 14 2018
%e A023138 a(11) = 2 because the function 6x mod 11 has the two cycles (0),(1,6,3,7,9,10,5,8,4,2).
%t A023138 CountFactors[p_, n_] := Module[{sum=0, m=n, d, f, i, ps, j}, ps=Transpose[FactorInteger[p]][[1]]; Do[While[Mod[m, ps[[j]]]==0, m/=ps[[j]]], {j, Length[ps]}]; d=Divisors[m]; Do[f=d[[i]]; sum+=EulerPhi[f]/MultiplicativeOrder[p, f], {i, Length[d]}]; sum]; Table[CountFactors[6, n], {n, 100}]
%o A023138 (Python)
%o A023138 from sympy import totient, n_order, divisors
%o A023138 def A023138(n):
%o A023138     m = n>>(~n & n-1).bit_length()
%o A023138     a, b = divmod(m,3)
%o A023138     while not b:
%o A023138         m = a
%o A023138         a, b = divmod(m,3)
%o A023138     return sum(totient(d)//n_order(6,d) for d in divisors(m,generator=True) if d>1)+1 # _Chai Wah Wu_, Apr 09 2024
%Y A023138 Cf. A000374.
%Y A023138 Cf. A023135, A023136, A023137, A023139, A023140, A023141, A023142.
%K A023138 nonn
%O A023138 1,5
%A A023138 _David W. Wilson_