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

Links

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

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

Example

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

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

Prog

(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

Crossrefs

Cf. A000374.

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

Sequence in context: A183201 A082467 A106407 * A283324 A072650 A082497

Adjacent sequences: A023138 A023139 A023140 * A023142 A023143 A023144

Keyword

nonn,changed

Author

David W. Wilson

Status

approved