A023141 - OEIS

%I #27 Apr 10 2024 03:30:35

%S 1,2,1,4,3,2,3,8,1,6,3,4,5,6,3,12,3,2,3,12,3,6,3,8,5,10,1,12,3,6,3,16,

%T 3,6,9,4,5,6,5,24,11,6,3,12,3,6,3,12,5,10,3,20,3,2,9,24,3,6,3,12,13,6,

%U 3,20,15,6,7,12,3,18,3,8,13,10,5,12,9,10,3,44,1,22,3,12,13,6,3,24,3,6,31,12,3

%N Number of cycles of function f(x) = 9x mod n.

%H T. D. Noe, <a href="/A023141/b023141.txt">Table of n, a(n) for n = 1..10000</a>

%F a(n) = Sum_{d|m} phi(d)/ord(9, d), where m is n with all factors of 3 removed. - _T. D. Noe_, Apr 21 2003

%F a(n) = (1/ord(9,m))*Sum_{j = 0..ord(9,m)-1} gcd(9^j - 1, m), where m is n with all factors of 3 removed. - _Nihar Prakash Gargava_, Nov 14 2018

%e a(12) = 4 because the function 9x mod 12 has the four cycles (0),(3),(1,9),(2,6).

%t 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[9, n], {n, 100}]

%o (Python)

%o from sympy import totient, n_order, divisors

%o def A023141(n):

%o     a, b = divmod(n,3)

%o     while not b:

%o         n = a

%o         a, b = divmod(n,3)

%o     return sum(totient(d)//n_order(9,d) for d in divisors(n,generator=True) if d>1)+1 # _Chai Wah Wu_, Apr 09 2024

%Y Cf. A000374.

%Y Cf. A023135, A023136, A023137, A023138, A023139, A023140, A023142.

%K nonn

%O 1,2

%A _David W. Wilson_