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

Offset: 2

Author

Robert G. Wilson v, Oct 11 2000

Keywords

• nonn
• easy
• nice

Comments

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

Examples

			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.
		

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]

Crossrefs

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

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

Programs

PARI

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