login
A087481
Number of polynomials of the form x^n +- x^(n-1) +- x^(n-2) +- ... +- 1 irreducible over the integers.
2
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,1
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
FORMULA
a(n) = 2^n for n a term of A071642; see first comment.
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}]
PROG
(SageMath) R.<x>=Z[]; a(n) = sum((x^n + sum(( 2 * ((b & (1<<d)) >> d) - 1 ) * x^d for d in range(n))).is_irreducible() for b in range(2^n))
CROSSREFS
Cf. A001122, A071642, A087482 (irreducible binary polynomials).
Sequence in context: A246047 A079102 A071337 * A038210 A244640 A230874
KEYWORD
nonn,hard,more
AUTHOR
T. D. Noe, Sep 09 2003
EXTENSIONS
a(19) from Robert Israel, Dec 22 2014
a(20)-a(27) from Lucas A. Brown, May 19 2023
STATUS
approved