A087482 Number of binary polynomials of degree n irreducible over the integers.

2, 2, 2, 6, 8, 21, 34, 84, 150, 331, 614, 1417, 2638, 5508, 10874, 23437, 44862, 95887, 185238, 390297, 765510, 1557427, 3043918, 6525948, 12706892, 25836122, 51135384, 105070336, 206266718, 426254492

Offset: 1

Author

T. D. Noe, Sep 09 2003

Keywords

• nonn
• more

Comments

A binary polynomial is defined as a monic polynomial whose remaining coefficients are either 0 or 1. For each n, there are 2^n polynomials to consider.

Links

• Eric Weisstein's World of Mathematics, Irreducible Polynomial

Crossrefs

Cf. A087481 (irreducible polynomials of the form x^n +- x^(n-1) +- x^(n-2) +- ... +- 1).

Cf. A001037 (irreducible polynomials over GF(2)).

Programs

Mathematica

Irreducible[p_, n_] := Module[{f}, f=FactorList[p, Modulus->n]; Length[f]==1 || Simplify[p-f[[2, 1]]]===0]; Table[xx=x^Range[0, n-1]; cnt=0; Do[p=x^n+xx.(IntegerDigits[i, 2, n]); If[Irreducible[p, 0], cnt++ ], {i, 0, 2^n-1}]; cnt, {n, 16}]

PARI

a(n)= { if( n<=2, return(2)); my(d, P, ct=0, x='x);  forstep (k=1, 2^n-1, 2, P=x^n+Pol(binary(k),x); ct+=polisirreducible(P) );  return(ct); }
for(n=1,30,print1(a(n),", ")); \\ Joerg Arndt, Dec 22 2014

Formula

a(n) >= A001037(n). - Joerg Arndt, Dec 22 2014

Extensions

Added more terms, Joerg Arndt, Dec 22 2014

a(23)-a(30) from Max Alekseyev, May 07 2022