%I #42 Apr 10 2024 03:29:57

%S 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 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 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 Number of cycles (mod n) under doubling map.

%C 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 GF(2). - _T. D. Noe_, Apr 16 2003

%D R. Lidl and H. Niederreiter, Finite Fields, Addison-Wesley, 1983, p. 65.

%H T. D. Noe, <a href="/A000374/b000374.txt">Table of n, a(n) for n = 1..10000</a>

%H Jarkko Peltomäki and Aleksi Saarela, <a href="https://doi.org/10.1016/j.jcta.2020.105340">Standard words and solutions of the word equation X_1^2 ... X_n^2 = (X_1 ... X_n)^2</a>, Journal of Combinatorial Theory, Series A (2021) Vol. 178, 105340. See also <a href="https://arxiv.org/abs/2004.14657">arXiv:2004.14657</a> [cs.FL], 2020.

%F 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

%F 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

%e 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 Table[Length[FactorList[x^n - 1, Modulus -> 2]] - 1, {n, 100}]

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

%o (PARI) a(n)={sumdiv(n >> valuation(n,2), d, eulerphi(d)/znorder(Mod(2,d)));}

%o vector(100,n,a(n)) \\ _Andrew Howroyd_, Nov 12 2018

%o (Python)

%o from sympy import totient, n_order, divisors

%o def A000374(n): return sum(totient(d)//n_order(2,d) for d in divisors(n>>(~n & n-1).bit_length(),generator=True) if d>1)+1 # _Chai Wah Wu_, Apr 09 2024

%Y Cf. A000005, A023135-A023142.

%Y Cf. A081844 (number of irreducible factors of x^(2n+1) - 1 over GF(2)).

%Y Cf. A037226 (number of primitive irreducible factors of x^(2n+1) - 1 over integers mod 2).

%K nonn

%O 1,3

%A _Shel Kaphan_