

A023137


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


7



1, 2, 2, 4, 1, 4, 2, 6, 3, 2, 3, 8, 4, 4, 2, 8, 2, 6, 3, 4, 5, 6, 2, 14, 1, 8, 4, 8, 3, 4, 11, 10, 6, 4, 2, 12, 2, 6, 11, 6, 3, 10, 2, 12, 3, 4, 2, 20, 3, 2, 5, 16, 2, 8, 3, 14, 6, 6, 3, 8, 3, 22, 12, 12, 4, 12, 4, 8, 5, 4, 15, 22, 2, 4, 2, 12, 6, 22, 3, 8, 5, 6, 2, 20, 2, 4, 8, 18, 3, 6, 11, 8, 22, 4, 3, 26
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

Number of factors in the factorization of the polynomial x^n1 over the integers mod 5.  T. D. Noe, Apr 16 2003


REFERENCES

R. Lidl and H. Niederreiter, Finite Fields, AddisonWesley, 1983, p. 65.


LINKS

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


FORMULA

a(n) = Sum_{dm} phi(d)/ord(5, d), where m is n with all factors of 5 removed.  T. D. Noe, Apr 19 2003
a(n) = (1/ord(5,m))*Sum_{j = 0..ord(5,m)1} gcd(5^j  1, m), where m is n with all factors of 5 removed.  Nihar Prakash Gargava, Nov 14 2018


EXAMPLE

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


MATHEMATICA

Table[Length[FactorList[x^n  1, Modulus > 5]]  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[5, n], {n, 100}]


CROSSREFS

Cf. A000005, A000374.
Cf. A023135, A023136, A023138, A023139, A023140, A023141, A023142.
Sequence in context: A264799 A248503 A214714 * A065273 A140819 A138558
Adjacent sequences: A023134 A023135 A023136 * A023138 A023139 A023140


KEYWORD

nonn


AUTHOR

David W. Wilson


STATUS

approved



