%I A000374
%S A000374 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,
%T A000374 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,
%U A000374 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
%N A000374 Number of cycles (mod n) under doubling map.
%C A000374 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 (noe(AT)sspectra.com), Apr 16 2003
%D A000374 R. Lidl and H. Niederreiter, Finite Fields, Addison-Wesley, 1983, p. 
               65.
%H A000374 T. D. Noe, <a href="b000374.txt">Table of n, a(n) for n=1..10000</a>
%F A000374 a(n) = Sum_{d|m} phi(d)/ord(2, d), where m is n with all factors of 2 
               removed. - T. D. Noe (noe(AT)sspectra.com), Apr 19 2003
%e A000374 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.
%t A000374 Table[Length[FactorList[x^n - 1, Modulus -> 2]] - 1, {n, 100}]
%t A000374 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}]
%Y A000374 Cf. A000005, A023135-A023142.
%Y A000374 Cf. A081844 (number of irreducible factors of x^(2n+1) - 1 over GF(2)).
%Y A000374 Cf. A037226 (number of primitive irreducible factors of x^(2n+1) - 1 
               over integers mod 2).
%Y A000374 Sequence in context: A054717 A086421 A109400 this_sequence A120562 A033666 
               A139124
%Y A000374 Adjacent sequences: A000371 A000372 A000373 this_sequence A000375 A000376 
               A000377
%K A000374 nonn
%O A000374 1,3
%A A000374 Shel Kaphan (sjk(AT)amazon.com)