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

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.

Links

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

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).

Example

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.

Prog

(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))

Crossrefs

Sequence in context: A257515 A105152 A066346 * A054233 A054231 A054230

Adjacent sequences: A175387 A175388 A175389 * A175391 A175392 A175393

Keyword

nonn

Author

Joerg Arndt, Apr 27 2010

Extensions

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

Status

approved