cp's OEIS Frontend

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

%I A344141 #18 May 11 2021 08:42:39
%S A344141 2,7,11,19,37,67,131,283,515,1033,2053,4105,8219,16417,32771,65579,
%T A344141 131081,262153,524327,1048585,2097157,4194307,8388641,16777243,
%U A344141 33554441,67108891,134217767,268435459,536870917,1073741827,2147483657,4294967437,8589934667
%N A344141 Lexicographically first irreducible polynomial over GF(2) of degree n, evaluated at X = 2.
%C A344141 a(n) is the smallest term in A014580 that is greater than or equal to 2^n.
%C A344141 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.
%C A344141 Note that in general you do not get an irreducible polynomial with the lowest possible number of terms, see A344142 and A344143.
%C A344141   N | The smallest n with |     The corresponding polynomial of degree n
%C A344141     |  A000120(a(n)) = N  |
%C A344141   1 |                   1 |                                                 x
%C A344141   3 |                   2 |                                       x^2 + x + 1
%C A344141   5 |                   8 |                           x^8 + x^4 + x^3 + x + 1
%C A344141   7 |                  37 |              x^37 + x^5 + x^4 + x^3 + x^2 + x + 1
%C A344141   9 |                 149 | x^149 + x^9 + x^7 + x^6 + x^5 + x^4 + x^3 + x + 1
%C A344141 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.
%H A344141 Jianing Song, <a href="/A344141/b344141.txt">Table of n, a(n) for n = 1..1000</a>
%e A344141 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.
%e A344141 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.
%o A344141 (PARI) A344141(n) = for(k=2^n, 2^(n+1)-1, if(polisirreducible(Mod(Pol(binary(k)), 2)), return(k)))
%Y A344141 Cf. A014580, A344142, A344143, A000120, A057496.
%K A344141 nonn
%O A344141 1,1
%A A344141 _Jianing Song_, May 10 2021