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

2, 4, 4, 16, 12, 48, 64, 192, 260, 1024, 1128, 4096, 4480, 13310, 20620, 65434, 76376, 262144, 358532, 932134, 1391720, 4194090, 5447256, 16570740, 23153832, 61696126, 97361128

Offset: 1

Author

T. D. Noe, Sep 09 2003

Keywords

• nonn
• hard
• more

Comments

For each n, there are 2^n polynomials to consider. All 2^n polynomials are irreducible for n = 1, 2, 4, 10, 12, 18, which is sequence A071642. For those values of n, n+1 is a prime in Artin's primitive root conjecture (A001122).

Since p(x) is irreducible iff (-1)^n*p(-x) is irreducible, all terms are even. - Robert Israel, Dec 22 2014

Links

• Eric Weisstein's World of Mathematics, Irreducible Polynomial
• Math Overflow, Irreducible polynomials with constrained coefficients

Crossrefs

Cf. A001122, A071642, A087482 (irreducible binary polynomials).

Programs

Maple

f:= proc(n) local t, j, p0, p;
   p0:= add(x^j, j = 0 .. n);
   2*nops(select(s -> irreduc(p0 - 2*add(x^(j-1), j = s)), combinat:-powerset(n-1)));
end proc:
seq(f(n),n=1..18); # Robert Israel, 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.(2*IntegerDigits[i, 2, n]-1); If[Irreducible[p, 0], cnt++ ], {i, 0, 2^n-1}]; cnt, {n, 18}]

SageMath

R.=Z[]; a(n) = sum((x^n + sum(( 2 * ((b & (1<> d) - 1 ) * x^d for d in range(n))).is_irreducible() for b in range(2^n))

Formula

a(n) = 2^n for n a term of A071642; see first comment.

Extensions

a(19) from Robert Israel, Dec 22 2014

a(20)-a(27) from Lucas A. Brown, May 19 2023