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

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

Table of n, a(n) for n=1..30.

Eric Weisstein's World of Mathematics, Irreducible Polynomial

Formula

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

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}]

Prog

(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

Crossrefs

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

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

Sequence in context: A298745 A323860 A121698 * A137227 A323862 A291667

Adjacent sequences: A087479 A087480 A087481 * A087483 A087484 A087485

Keyword

nonn,more

Author

T. D. Noe, Sep 09 2003

Extensions

Added more terms, Joerg Arndt, Dec 22 2014

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

Status

approved