

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^n1 over the integers mod 2.  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(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^141 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, A023135A023142.
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: A176853 A261787 A302480 * A256757 A277314 A120562
Adjacent sequences: A000371 A000372 A000373 * A000375 A000376 A000377


KEYWORD

nonn


AUTHOR

Shel Kaphan


STATUS

approved



