%I #26 May 19 2023 08:02:27
%S 2,4,4,16,12,48,64,192,260,1024,1128,4096,4480,13310,20620,65434,
%T 76376,262144,358532,932134,1391720,4194090,5447256,16570740,23153832,
%U 61696126,97361128
%N Number of polynomials of the form x^n +- x^(n-1) +- x^(n-2) +- ... +- 1 irreducible over the integers.
%C 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).
%C Since p(x) is irreducible iff (-1)^n*p(-x) is irreducible, all terms are even. - _Robert Israel_, Dec 22 2014
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/IrreduciblePolynomial.html">Irreducible Polynomial</a>
%H Math Overflow, <a href="http://mathoverflow.net/questions/7969/irreducible-polynomials-with-constrained-coefficients/8086#8086">Irreducible polynomials with constrained coefficients</a>
%F a(n) = 2^n for n a term of A071642; see first comment.
%p f:= proc(n) local t, j, p0, p;
%p p0:= add(x^j, j = 0 .. n);
%p 2*nops(select(s -> irreduc(p0 - 2*add(x^(j-1), j = s)), combinat:-powerset(n-1)));
%p end proc:
%p seq(f(n),n=1..18); # _Robert Israel_, Dec 22 2014
%t 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}]
%o (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))
%Y Cf. A001122, A071642, A087482 (irreducible binary polynomials).
%K nonn,hard,more
%O 1,1
%A _T. D. Noe_, Sep 09 2003
%E a(19) from _Robert Israel_, Dec 22 2014
%E a(20)-a(27) from _Lucas A. Brown_, May 19 2023
|