A081844 - OEIS

%I #44 Apr 10 2024 03:30:43

%S 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 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 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 Number of irreducible factors of x^(2n+1) - 1 over GF(2).

%C Also number of nonisomorphic "pure" chain rings with certain parameters.

%C Number of cycles under doubling map x -> 2*x  (mod 2*n+1). - _Joerg Arndt_, Jan 22 2024

%D R. Lidl and H. Niederreiter, Finite Fields, Addison-Wesley, 1983; Theorem 2.47 page 65.

%H T. D. Noe, <a href="/A081844/b081844.txt">Table of n, a(n) for n = 0..10000</a>

%H 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 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 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 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 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 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 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 a(n) = Sum_{ d| 2*n+1 } phi(d)/ord_2(d), where phi = A000010, ord_2 = A002326.

%F a(n) = A006694(n) + 1. - _Joerg Arndt_, Apr 01 2019

%F a(n) = A000374(2*n+1). - _Joerg Arndt_, Jan 22 2024

%p 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 Factor(x^(2*n+1)-1) mod 2; nops(%);

%t a[n_] := Length[Factor[x^(2n+1)-1, Modulus->2] ]; a[0]=1; (* or : *)

%t 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 (PARI) a(n)=sumdiv(2*n+1,d,eulerphi(d)/znorder(Mod(2,d)));

%o vector(122,n,a(n-1)) /* _Joerg Arndt_, Jan 18 2011 */

%o (Python)

%o from sympy import totient, n_order, divisors

%o 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 Cf. A001037.

%Y A000374 gives number of factors of x^n-1 for any n.

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

%Y Cf. A006694 (number of factors of (x^(2*n+1) - 1) / (x - 1) over GF(2) ).

%K nonn

%O 0,2

%A _N. J. A. Sloane_, Apr 11 2003