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

Links

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

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

Example

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

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}]

Prog

(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

Crossrefs

Cf. A000374.

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

Sequence in context: A295882 A127551 A256547 * A194704 A108170 A086988

Adjacent sequences: A023135 A023136 A023137 * A023139 A023140 A023141

Keyword

nonn

Author

David W. Wilson

Status

approved