This site is supported by donations to The OEIS Foundation.

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A023135 Number of cycles of function f(x) = 3x mod n. 10
 1, 2, 1, 3, 2, 2, 2, 5, 1, 4, 3, 3, 5, 4, 2, 7, 2, 2, 2, 7, 2, 6, 3, 5, 3, 10, 1, 7, 2, 4, 2, 9, 3, 4, 5, 3, 3, 4, 5, 13, 6, 4, 2, 9, 2, 6, 3, 7, 3, 6, 2, 15, 2, 2, 6, 13, 2, 4, 3, 7, 7, 4, 2, 11, 10, 6, 4, 7, 3, 10, 3, 5, 7, 6, 3, 7, 6, 10, 2, 23, 1, 12, 3, 7, 7, 4, 2, 15, 2, 4, 18, 9, 2, 6, 5, 9, 3, 6, 3, 11 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,2 COMMENTS Number of factors in the factorization of the polynomial x^n-1 over the integers mod 3. - 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(3, d), where m is n with all factors of 3 removed. - T. D. Noe, Apr 19 2003 a(n) = (1/ord(3,m))*Sum_{j = 0..ord(3,m)-1} gcd(3^j - 1, m), where m is n with all factors of 3 removed. - Nihar Prakash Gargava, Nov 14 2018 EXAMPLE a(15) = 2 because (1) the function 3x mod 15 has the two cycles (0),(3,9,12,6) and (2) the factorization of x^15-1 over integers mod 3 is (2+x)^3 (1+x+x^2+x^3+x^4)^3, 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 -> 3]] - 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[3, n], {n, 100}] CROSSREFS Cf. A000005, A000374. Cf. A023136, A023137, A023138, A023139, A023140, A023141, A023142. Sequence in context: A276166 A177062 A133924 * A191654 A205784 A066272 Adjacent sequences:  A023132 A023133 A023134 * A023136 A023137 A023138 KEYWORD nonn AUTHOR STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified January 17 06:41 EST 2019. Contains 319207 sequences. (Running on oeis4.)