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

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, 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, 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

Offset: 0

Author

N. J. A. Sloane, Apr 11 2003

Keywords

• nonn

Comments

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

Number of cycles under doubling map x -> 2*x (mod 2*n+1). - Joerg Arndt, Jan 22 2024

References

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

Links

• T. D. Noe, Table of n, a(n) for n = 0..10000
• Jean-Paul Allouche, Manon Stipulanti, and Jia-Yan Yao, Doubling modulo odd integers, generalizations, and unexpected occurrences, arXiv:2504.17564 [math.NT], 2025.
• G. Chassé, Combinatorial cycles of a polynomial map over a commutative field, Discrete Math. 61 (1986), 21-26.
• E. W. Clark and J. J. Liang, Enumeration of finite commutative chain rings, J. Algebra 27 (1973), 445-453.
• Pieter Moree, Number of irreducible factors of x^n-1 over a finite field, Posting to Number Theory List, Apr 11, 2003.
• T. D. Rogers, The graph of the square mapping on the prime fields, Discrete Math. 148 (1996), 317-324
• D. Ulmer, Elliptic curves with large rank over function fields, Ann. of Math. 155 (2002), 295-315
• D. Ulmer, Elliptic curves with large rank over function fields, arXiv:math/0109163 [math.NT].
• Troy Vasiga and Jeffrey Shallit, On the iteration of certain quadratic maps over GF(p), Discrete Mathematics, Volume 277, Issues 1-3, 2004, pages 219-240.

Crossrefs

Cf. A001037.

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

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

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

Programs

Maple

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

Mathematica

a[n_] := Length[Factor[x^(2n+1)-1, Modulus->2] ]; a[0]=1; (* or : *)
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 *)

PARI

a(n)=sumdiv(2*n+1,d,eulerphi(d)/znorder(Mod(2,d)));
vector(122,n,a(n-1)) /* Joerg Arndt, Jan 18 2011 */

Python

from sympy import totient, n_order, divisors
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

Formula

a(n) = Sum_{ d| 2*n+1 } phi(d)/ord_2(d), where phi = A000010, ord_2 = A002326.

a(n) = A006694(n) + 1. - Joerg Arndt, Apr 01 2019

a(n) = A000374(2*n+1). - Joerg Arndt, Jan 22 2024