A023141 Number of cycles of function f(x) = 9x mod n.
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, 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, 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
Offset: 1
Keywords
Examples
a(12) = 4 because the function 9x mod 12 has the four cycles (0),(3),(1,9),(2,6).
Links
- T. D. Noe, Table of n, a(n) for n = 1..10000
Programs
-
Mathematica
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}] -
Python
from sympy import totient, n_order, divisors def A023141(n): a, b = divmod(n,3) while not b: n = a a, b = divmod(n,3) 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
Formula
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
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