cp's OEIS Frontend

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

%I A175390 #20 Jun 25 2021 23:15:07
%S A175390 1,1,0,1,2,2,4,9,14,24,48,86,154,294,550,1017,1926,3654,6888,13092,
%T A175390 24998,47658,91124,174822,335588,645120,1242822,2396970,4627850,
%U A175390 8947756,17319148,33553881,65074406,126324420,245426486,477215270,928645186
%N A175390 Number of irreducible binary polynomials Sum_{j=0..n} c(j)*x^j with c(1)=c(n-1)=1.
%C A175390 Binary polynomial means polynomial over GF(2).
%C A175390 A formula for the enumeration is given in Niederreiter's paper, see the PARI/GP code.
%C A175390 a(n) > 0 for n > 3.
%H A175390 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 A175390 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 A175390 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 A175390 (PARI)
%o A175390 A(n) = {
%o A175390 my( h, m, ret );
%o A175390 if ( n==1, return(1) );
%o A175390 h = valuation(n,2); /* largest power of 2 dividing n */
%o A175390 m = n/2^h; /* odd part of n */
%o A175390 if ( m == 1, /* power of two */
%o A175390   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 A175390 , /* else */
%o A175390   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 A175390 );
%o A175390 return( ret );
%o A175390 }
%o A175390 vector(50,n,A(n))
%K A175390 nonn
%O A175390 1,5
%A A175390 _Joerg Arndt_, Apr 27 2010
%E A175390 Edited by _Franklin T. Adams-Watters_, May 12 2010