|
%I #20 Jun 25 2021 23:15:07
%S 1,1,0,1,2,2,4,9,14,24,48,86,154,294,550,1017,1926,3654,6888,13092,
%T 24998,47658,91124,174822,335588,645120,1242822,2396970,4627850,
%U 8947756,17319148,33553881,65074406,126324420,245426486,477215270,928645186
%N Number of irreducible binary polynomials Sum_{j=0..n} c(j)*x^j with c(1)=c(n-1)=1.
%C Binary polynomial means polynomial over GF(2).
%C A formula for the enumeration is given in Niederreiter's paper, see the PARI/GP code.
%C a(n) > 0 for n > 3.
%H Alp Bassa, Ricardo Menares, <a href="https://arxiv.org/abs/1905.08345">Enumeration of a special class of irreducible polynomials in characteristic 2</a>, arXiv:1905.08345 [math.NT], 2019.
%H Harald Niederreiter, <a href="https://doi.org/10.1007/BF01810295">An enumeration formula for certain irreducible polynomials with an application to the construction of irreducible polynomials over the binary field</a>, Applicable Algebra in Engineering, Communication and Computing, vol. 1, no. 2, pp. 119-124, (September-1990).
%e 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.
%o (PARI)
%o A(n) = {
%o my( h, m, ret );
%o if ( n==1, return(1) );
%o h = valuation(n,2); /* largest power of 2 dividing n */
%o m = n/2^h; /* odd part of n */
%o if ( m == 1, /* power of two */
%o ret = (2^n+1)/(4*n) - 1/(2^(n+1)*n) * sum(j=0, n/2, (-1)^j*binomial(n,2*j)*7^j);
%o , /* else */
%o 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) ) );
%o );
%o return( ret );
%o }
%o vector(50,n,A(n))
%K nonn
%O 1,5
%A _Joerg Arndt_, Apr 27 2010
%E Edited by _Franklin T. Adams-Watters_, May 12 2010
|
