A057646 - OEIS

A057646

a(n) is the number of trinomials x^n + x^k + 1 that are irreducible over GF(2) for some k with n > k > 0.

1, 2, 2, 2, 3, 4, 0, 4, 2, 2, 4, 0, 2, 6, 0, 6, 5, 0, 4, 4, 2, 4, 0, 4, 0, 0, 8, 2, 4, 8, 0, 4, 2, 2, 6, 0, 0, 6, 0, 4, 2, 0, 2, 0, 2, 8, 0, 8, 0, 0, 8, 0, 5, 4, 0, 8, 2, 0, 12, 0, 2, 10, 0, 4, 2, 0, 4, 0, 0, 10, 0, 6, 2, 0, 2, 0, 0, 4, 0, 6, 0, 0, 14, 0, 2, 2, 0, 2, 2, 0, 2, 2, 2, 4, 0, 8, 4, 0, 10

(list; graph; refs; listen; history; text; internal format)

OFFSET

2,2

COMMENTS

Brent, Hart, Kruppa, and Zimmermann found that a(57885161) = 0. - Charles R Greathouse IV, May 30 2013

LINKS

T. D. Noe, Table of n, a(n) for n = 2..500

Paul Zimmermann, There is no primitive trinomial of degree 57885161 over GF(2), posting to NMBRTHRY mailing list [alternate link]

EXAMPLE

a(7) = 4 because 1 + x + x^7 = 1 + x + x^7, 1 + x^2 + x^7 = (1 + x + x^2)*(1 + x + x^2 + x^4 + x^5), 1 + x^3 + x^7 = 1 + x^3 + x^7, 1 + x^4 + x^7 = 1 + x^4 + x^7, 1 + x^5 + x^7 = (1 + x + x^2)*(1 + x + x^3 + x^4 + x^5) and 1 + x^6 + x^7 = 1 + x^6 + x^7. Thus there are 4 trinomial expressions which cannot be factored over GF(2) and 2 trinomial expressions which do factor.

PROG

(PARI) a(n)=sum(s=1, n-1, polisirreducible((x^n+x^s+1)*Mod(1, 2))) \\ Charles R Greathouse IV, May 30 2013

CROSSREFS

For n such that a(n) > 0 see A073571.

Cf. A014580 (irreducible polynomials over GF(2) encoded as binary numbers), A344146.

Sequence in context: A348626 A124492 A338629 * A238892 A238279 A282933

Adjacent sequences: A057643 A057644 A057645 * A057647 A057648 A057649

KEYWORD

nonn,easy,nice

AUTHOR

Robert G. Wilson v, Oct 11 2000

STATUS

approved