A023139 Number of cycles of function f(x) = 7x mod n.

1, 2, 3, 3, 2, 6, 1, 5, 5, 4, 2, 9, 2, 2, 6, 9, 2, 10, 7, 7, 3, 4, 2, 15, 7, 4, 7, 3, 5, 12, 3, 13, 6, 4, 2, 15, 5, 14, 6, 13, 2, 6, 8, 7, 10, 4, 3, 27, 1, 14, 6, 7, 3, 14, 5, 5, 21, 10, 3, 21, 2, 6, 5, 17, 7, 12, 2, 7, 6, 4, 2, 25, 4, 10, 21, 21, 2, 12, 2, 25, 9, 4, 3, 9, 7, 16, 15, 13, 2, 20, 2, 7, 9, 6

Offset

1,2

Comments

Number of factors in the factorization of the polynomial x^n-1 over GF(7). - T. D. Noe, Apr 16 2003

References

R. Lidl and H. Niederreiter, Finite Fields, Addison-Wesley, 1983, p. 65.

Links

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

Formula

a(n) = Sum_{d|m} phi(d)/ord(7, d), where m is n with all factors of 7 removed. - T. D. Noe, Apr 19 2003

a(n) = (1/ord(7,m))*Sum_{j = 0..ord(7,m)-1} gcd(7^j - 1, m), where m is n with all factors of 7 removed. - Nihar Prakash Gargava, Nov 14 2018

Example

a(8) = 5 because (1) the function 7x mod 8 has the five cycles (0),(4),(1,7),(2,6),(3,5) and (2) the factorization of x^8-1 over integers mod 7 is (1+x) (6+x) (1+x^2) (1+3x+x^2) (1+4x+x^2), which has five unique factors. Note that the length of the cycles is the same as the degree of the factors.
a(10) = 2 because the function 8x mod 10 has the two cycles (0),(2,6,8,4).

Mathematica

Table[Length[FactorList[x^n - 1, Modulus -> 7]] - 1, {n, 100}]
CountFactors[p_, n_] := Module[{sum=0, m=n, d, f, i}, While[Mod[m, p]==0, m/=p]; d=Divisors[m]; Do[f=d[[i]]; sum+=EulerPhi[f]/MultiplicativeOrder[p, f], {i, Length[d]}]; sum]; Table[CountFactors[7, n], {n, 100}]

Prog

(PARI) a(n)={sumdiv(n/7^valuation(n, 7), d, eulerphi(d)/znorder(Mod(7, d))); }
vector(100, n, a(n)) \\ Joerg Arndt, Jan 22 2024
(Python)
from sympy import totient, n_order, divisors
def A023139(n):
    a, b = divmod(n, 7)
    while not b:
        n = a
        a, b = divmod(n, 7)
    return sum(totient(d)//n_order(7, d) for d in divisors(n, generator=True) if d>1)+1 # Chai Wah Wu, Apr 09 2024

Crossrefs

Cf. A000005, A000374.

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

Sequence in context: A238114 A291300 A345287 * A328484 A319442 A299772

Adjacent sequences: A023136 A023137 A023138 * A023140 A023141 A023142

Keyword

nonn

Author

David W. Wilson

Status

approved