The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A000374 Number of cycles (mod n) under doubling map. 19
 1, 1, 2, 1, 2, 2, 3, 1, 3, 2, 2, 2, 2, 3, 5, 1, 3, 3, 2, 2, 6, 2, 3, 2, 3, 2, 4, 3, 2, 5, 7, 1, 5, 3, 6, 3, 2, 2, 5, 2, 3, 6, 4, 2, 8, 3, 3, 2, 5, 3, 8, 2, 2, 4, 5, 3, 5, 2, 2, 5, 2, 7, 13, 1, 7, 5, 2, 3, 6, 6, 3, 3, 9, 2, 8, 2, 6, 5, 3, 2, 5, 3, 2, 6, 12, 4, 5, 2, 9, 8, 10, 3, 14, 3, 5, 2, 3, 5, 8, 3 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,3 COMMENTS Number of cycles of the function f(x) = 2x mod n. Number of irreducible factors in the factorization of the polynomial x^n-1 over the integers mod 2. - 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(2, d), where m is n with all factors of 2 removed. - T. D. Noe, Apr 19 2003 a(n) = (1/ord(2,m))*Sum_{j = 0..ord(2,m)-1} gcd(2^j - 1, m), where m is n with all factors of 2 removed. - Nihar Prakash Gargava, Nov 12 2018 EXAMPLE a(14) = 3 because (1) the function 2x mod 14 has the three cycles (0),(2,4,8),(6,12,10) and (2) the factorization of x^14-1 over integers mod 2 is (1+x)^2 (1+x+x^3)^2 (1+x^2+x^3)^2, which has three 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 -> 2]] - 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[2, n], {n, 100}] PROG (PARI) a(n)={sumdiv(n >> valuation(n, 2), d, eulerphi(d)/znorder(Mod(2, d)))} \\ Andrew Howroyd, Nov 12 2018 CROSSREFS Cf. A000005, A023135-A023142. Cf. A081844 (number of irreducible factors of x^(2n+1) - 1 over GF(2)). Cf. A037226 (number of primitive irreducible factors of x^(2n+1) - 1 over integers mod 2). Sequence in context: A261787 A302480 A329656 * A256757 A333860 A277314 Adjacent sequences:  A000371 A000372 A000373 * A000375 A000376 A000377 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 September 18 04:44 EDT 2020. Contains 337165 sequences. (Running on oeis4.)