

A175390


Number of irreducible binary polynomials sum(j=0..n, c(j)*x^j) with c(1)=c(n1)=1.


0



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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.


REFERENCES

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.119124, (September1990)


LINKS

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


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^(12^h*d)*sum(j=0, floor(2^(h1)*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. AdamsWatters, May 12 2010


STATUS

approved



