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

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

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.

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

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 *)

Prog

(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

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) ).

Sequence in context: A049113 A055093 A196058 * A233549 A334475 A110012

Adjacent sequences: A081841 A081842 A081843 * A081845 A081846 A081847

Keyword

nonn

Author

N. J. A. Sloane, Apr 11 2003

Status

approved