A175390 Number of irreducible binary polynomials Sum_{j=0..n} c(j)*x^j with c(1)=c(n-1)=1.

1, 1, 0, 1, 2, 2, 4, 9, 14, 24, 48, 86, 154, 294, 550, 1017, 1926, 3654, 6888, 13092, 24998, 47658, 91124, 174822, 335588, 645120, 1242822, 2396970, 4627850, 8947756, 17319148, 33553881, 65074406, 126324420, 245426486, 477215270, 928645186

Offset: 1

Author

Joerg Arndt, Apr 27 2010

Keywords

• nonn

Comments

Binary polynomial means polynomial over GF(2).

A formula for the enumeration is given in Niederreiter's paper, see the PARI/GP code.

a(n) > 0 for n > 3.

Examples

			The only irreducible binary polynomial of degree 2 is x^2+x+1 and it has the required property, so a(2)=1. The only polynomials of degree 3 with c(1)=c(2)=1 are x^3+x^2+x and x^3+x^2+x+1; neither is irreducible, so a(3)=0.
		

Links

• Alp Bassa, Ricardo Menares, Enumeration of a special class of irreducible polynomials in characteristic 2, arXiv:1905.08345 [math.NT], 2019.
• Harald Niederreiter, An enumeration formula for certain irreducible polynomials with an application to the construction of irreducible polynomials over the binary field, Applicable Algebra in Engineering, Communication and Computing, vol. 1, no. 2, pp. 119-124, (September-1990).

Programs

PARI

A(n) = {
my( h, m, ret );
if ( n==1, return(1) );
h = valuation(n,2); /* largest power of 2 dividing n */
m = n/2^h; /* odd part of n */
if ( m == 1, /* power of two */
  ret = (2^n+1)/(4*n) - 1/(2^(n+1)*n) * sum(j=0, n/2, (-1)^j*binomial(n,2*j)*7^j);
, /* else */
  ret = 1/(4*n)*sumdiv(m,d, moebius(m/d) *(2^(2^h*d) - 2^(1-2^h*d)*sum(j=0, floor(2^(h-1)*d), (-1)^(2^h*d+j) * binomial(2^h*d,2*j)*7^j) ) );
);
return( ret );
}
vector(50,n,A(n))

Extensions

Edited by Franklin T. Adams-Watters, May 12 2010