|
|
A175390
|
|
Number of irreducible binary polynomials Sum_{j=0..n} c(j)*x^j with c(1)=c(n-1)=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
(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.
|
|
LINKS
|
|
|
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
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|