login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000374 Number of cycles (mod n) under doubling map. 16
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

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

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: A210868 A176853 A261787 * A256757 A277314 A120562

Adjacent sequences:  A000371 A000372 A000373 * A000375 A000376 A000377

KEYWORD

nonn

AUTHOR

Shel Kaphan

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified August 16 11:20 EDT 2017. Contains 290623 sequences.