login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 14 04:44 EDT 2019. Contains 327995 sequences. (Running on oeis4.)