A344143 -id:A344143 - cp's OEIS frontend

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

Jianing Song, May 10 2021

nonn

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.

			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.

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

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

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

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

Original entry on oeis.org

Offset: 1

Jianing Song, May 10 2021

nonn

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.

			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.

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

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

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.

cp's OEIS Frontend

A344141 Lexicographically first irreducible polynomial over GF(2) of degree n, evaluated at X = 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI