A344141 Lexicographically first irreducible polynomial over GF(2) of degree n, 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, 8589934667

Offset: 1

Author

Jianing Song, May 10 2021

Keywords

• nonn

Comments

a(n) is the smallest term in A014580 that is greater than or equal to 2^n.

To get a(n), you first ask the question: "Is x^n irreducible over GF(2)?" If it is not, you then ask "is x^n + 1 irreducible over GF(2)", then "is x^n + x irreducible over GF(2)", then "is x^n + x + 1 irreducible over GF(2)", until you get an irreducible polynomial, then evaluate it at x = 2.

Note that in general you do not get an irreducible polynomial with the lowest possible number of terms, see A344142 and A344143.

N | The smallest n with | The corresponding polynomial of degree n

| A000120(a(n)) = N |

1 | 1 | x

3 | 2 | x^2 + x + 1

5 | 8 | x^8 + x^4 + x^3 + x + 1

7 | 37 | x^37 + x^5 + x^4 + x^3 + x^2 + x + 1

9 | 149 | x^149 + x^9 + x^7 + x^6 + x^5 + x^4 + x^3 + x + 1

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(8) = 283, since x^8, x^8 + 1, x^8 + x, x^8 + x + 1, ..., x^8 + x^4 + x^3 + x are all reducible over GF(2) and x^8 + x^4 + x^3 + x + 1 is irreducible, so a(8) = 2^8 + 2^4 + 2^3 + 2 + 1 = 283.
a(33) = 8589934667, since x^33, x^33 + 1, x^33 + x, x^33 + x + 1, ..., x^33 + x^6 + x^3 + x are all reducible over GF(2) and x^33 + x^6 + x^3 + x + 1 is irreducible, so a(33) = 2^33 + 2^6 + 2^3 + 2 + 1 = 8589934667. Note that there is an irreducible trinomial of degree 33, namely x^33 + x^10 + 1.
		

Links

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

Crossrefs

Cf. A014580, A344142, A344143, A000120, A057496.

Programs

PARI

A344141(n) = for(k=2^n, 2^(n+1)-1, if(polisirreducible(Mod(Pol(binary(k)), 2)), return(k)))