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

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, 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, 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

Offset: 1

Author

David W. Wilson

Keywords

• nonn

Examples

			a(11) = 2 because the function 6x mod 11 has the two cycles (0),(1,6,3,7,9,10,5,8,4,2).
		

Links

• T. D. Noe, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000374.

Cf. A023135, A023136, A023137, A023139, A023140, A023141, A023142.

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[6, n], {n, 100}]

Python

from sympy import totient, n_order, divisors
def A023138(n):
    m = n>>(~n & n-1).bit_length()
    a, b = divmod(m,3)
    while not b:
        m = a
        a, b = divmod(m,3)
    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

Formula

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

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