This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A000374 #46 Apr 25 2025 03:06:11
%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 GF(2). - _T. D. Noe_, Apr 16 2003
%D A000374 R. Lidl and H. Niederreiter, Finite Fields, Addison-Wesley, 1983, p. 65.
%H A000374 T. D. Noe, <a href="/A000374/b000374.txt">Table of n, a(n) for n = 1..10000</a>
%H A000374 Jean-Paul Allouche, Manon Stipulanti, and Jia-Yan Yao, <a href="https://arxiv.org/abs/2504.17564">Doubling modulo odd integers, generalizations, and unexpected occurrences</a>, arXiv:2504.17564 [math.NT], 2025.
%H A000374 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 A000374 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 A000374 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 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}]
%o A000374 (PARI) a(n)={sumdiv(n >> valuation(n,2), d, eulerphi(d)/znorder(Mod(2,d)));}
%o A000374 vector(100,n,a(n)) \\ _Andrew Howroyd_, Nov 12 2018
%o A000374 (Python)
%o A000374 from sympy import totient, n_order, divisors
%o A000374 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 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).
%K A000374 nonn
%O A000374 1,3
%A A000374 _Shel Kaphan_