cp's OEIS Frontend

A081844 Number of irreducible factors of x^(2n+1) - 1 over GF(2).

%I A081844 #48 Apr 25 2025 03:06:57
%S A081844 1,2,2,3,3,2,2,5,3,2,6,3,3,4,2,7,5,6,2,5,3,4,8,3,5,8,2,5,5,2,2,13,7,2,
%T A081844 6,3,9,8,6,3,5,2,12,5,9,10,14,5,3,8,2,3,15,2,4,5,5,6,12,9,3,8,4,19,11,
%U A081844 2,10,11,3,2,6,5,7,10,2,11,13,14,4,5,9,2,14,3,3,12,2,9,5,2,2,5,7,8,20,3,3,20
%N A081844 Number of irreducible factors of x^(2n+1) - 1 over GF(2).
%C A081844 Also number of nonisomorphic "pure" chain rings with certain parameters.
%C A081844 Number of cycles under doubling map x -> 2*x  (mod 2*n+1). - _Joerg Arndt_, Jan 22 2024
%D A081844 R. Lidl and H. Niederreiter, Finite Fields, Addison-Wesley, 1983; Theorem 2.47 page 65.
%H A081844 T. D. Noe, <a href="/A081844/b081844.txt">Table of n, a(n) for n = 0..10000</a>
%H A081844 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 A081844 G. Chassé, <a href="http://dx.doi.org/10.1016/0012-365X(86)90024-5">Combinatorial cycles of a polynomial map over a commutative field</a>, Discrete Math. 61 (1986), 21-26.
%H A081844 E. W. Clark and J. J. Liang, <a href="http://dx.doi.org/10.1016/0021-8693(73)90055-0">Enumeration of finite commutative chain rings</a>, J. Algebra 27 (1973), 445-453.
%H A081844 Pieter Moree, <a href="https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;87dd13a3.0304">Number of irreducible factors of x^n-1 over a finite field</a>, Posting to Number Theory List, Apr 11, 2003.
%H A081844 T. D. Rogers, <a href="http://dx.doi.org/10.1016/0012-365X(94)00250-M">The graph of the square mapping on the prime fields</a>, Discrete Math. 148 (1996), 317-324
%H A081844 D. Ulmer, <a href="http://www.jstor.org/stable/3062158">Elliptic curves with large rank over function fields</a>, Ann. of Math. 155 (2002), 295-315
%H A081844 D. Ulmer, <a href="http://arxiv.org/abs/math/0109163">Elliptic curves with large rank over function fields</a>, arXiv:math/0109163 [math.NT].
%H A081844 Troy Vasiga and Jeffrey Shallit, <a href="http://dx.doi.org/10.1016/S0012-365X(03)00158-4">On the iteration of certain quadratic maps over GF(p)</a>, Discrete Mathematics, Volume 277, Issues 1-3, 2004, pages 219-240.
%F A081844 a(n) = Sum_{ d| 2*n+1 } phi(d)/ord_2(d), where phi = A000010, ord_2 = A002326.
%F A081844 a(n) = A006694(n) + 1. - _Joerg Arndt_, Apr 01 2019
%F A081844 a(n) = A000374(2*n+1). - _Joerg Arndt_, Jan 22 2024
%p A081844 with(numtheory); o := n->if n=1 then 1 else order(2,n); fi; A081844 := proc(n) local d, t1; t1 := 0; for d to n do if n mod d = 0 then t1 := t1 + phi(d)/o(d); end if; end do; t1; end proc;
%p A081844 Factor(x^(2*n+1)-1) mod 2; nops(%);
%t A081844 a[n_] := Length[Factor[x^(2n+1)-1, Modulus->2] ]; a[0]=1; (* or : *)
%t A081844 a[n_] := Sum[ EulerPhi[d] / MultiplicativeOrder[2, d ], {d, Divisors[2n + 1]}]; Table[ a[n], {n, 0, 97}] (* _Jean-François Alcover_, Dec 14 2011 *)
%o A081844 (PARI) a(n)=sumdiv(2*n+1,d,eulerphi(d)/znorder(Mod(2,d)));
%o A081844 vector(122,n,a(n-1)) /* _Joerg Arndt_, Jan 18 2011 */
%o A081844 (Python)
%o A081844 from sympy import totient, n_order, divisors
%o A081844 def A081844(n): return sum(totient(d)//n_order(2,d) for d in divisors((n+1<<1)-1,generator=True) if d>1) + 1 # _Chai Wah Wu_, Apr 09 2024
%Y A081844 Cf. A001037.
%Y A081844 A000374 gives number of factors of x^n-1 for any n.
%Y A081844 Cf. A037226 (number of primitive irreducible factors of x^(2n+1) - 1 over integers mod 2).
%Y A081844 Cf. A006694 (number of factors of (x^(2*n+1) - 1) / (x - 1) over GF(2) ).
%K A081844 nonn
%O A081844 0,2
%A A081844 _N. J. A. Sloane_, Apr 11 2003