A344142 Lexicographically first irreducible polynomial over GF(2) of degree n with the lowest possible number of terms, evaluated at X = 2.

2, 7, 11, 19, 37, 67, 131, 283, 515, 1033, 2053, 4105, 8219, 16417, 32771, 65579, 131081, 262153, 524327, 1048585, 2097157, 4194307, 8388641, 16777243, 33554441, 67108891, 134217767, 268435459, 536870917, 1073741827, 2147483657, 4294967437, 8589935617

Offset: 1

Author

Jianing Song, May 10 2021

Keywords

• nonn

Comments

Different from A344141, here you first check x^n + x + 1, x^n + x^2 + 1, ..., x^n + x^(n-1) + 1 until you get an irreducible polynomial over GF(2); if there are none, you then check x^n + x^3 + x^2 + x + 1, x^n + x^4 + x^2 + x + 1, x^n + x^4 + x^3 + x + 1, x^n + x^4 + x^3 + x^2 + 1, ..., x^n + x^(n-1) + x^(n-2) + x^(n-3) + 1 until you get an irreducible polynomial over GF(2). Once you find it, evaluate it at x = 2.

Note that it is conjectured that an irreducible polynomial of degree n with 5 terms exists for every n. It follows from the conjecture that A000120(a(n)) = 3 for n in A073571 and 5 for n in A057486.

In A057496 it is stated that if x^n + x^3 + x^2 + x + 1 is irreducible, then so is x^n + x^3 + 1. It follows that no term other than 19 can be of the form 2^n + 15.

Examples

			a(33) = 8589935617, since x^33 + x + 1, x^33 + x^2 + 1, x^33 + x^3 + 1, ..., x^33 + x^9 + 1 are all reducible over GF(2) and x^33 + x^10 + 1 is irreducible, so a(33) = 2^33 + 2^10 + 1 = 8589935617.
a(8) = 283, since x^8 + x + 1, x^8 + x^2 + 1, ..., x^8 + x^7 + 1 are all reducible over GF(2); both x^8 + x^3 + x^2 + x + 1, x^8 + x^4 + x^2 + x + 1 are reducible, and x^8 + x^4 + x^3 + x + 1 is irreducible, so a(8) = 2^8 + 2^4 + 2^3 + 2 + 1 = 283.
		

Links

• Jianing Song, Table of n, a(n) for n = 1..1000

Crossrefs

Cf. A014580, A344141, A344143, A000120, A073571, A057486, A057496.

Programs

PARI

A344142(n) = if(n==1, 2, for(k=1, n-1, if(polisirreducible(Mod(x^n+x^k+1, 2)), return(2^n+2^k+1))); for(a=3, n-1, for(b=2, a-1, for(c=1, b-1, if(polisirreducible(Mod(x^n+x^a+x^b+x^c+1, 2)), return(2^n+2^a+2^b+2^c+1)))))) \\ Assuming that an irreducible polynomial of degree n with at most 5 terms exists for every n.