OFFSET
1,1
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.
LINKS
Jianing Song, Table of n, a(n) for n = 1..1000
EXAMPLE
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.
PROG
(PARI) A344141(n) = for(k=2^n, 2^(n+1)-1, if(polisirreducible(Mod(Pol(binary(k)), 2)), return(k)))
CROSSREFS
KEYWORD
nonn
AUTHOR
Jianing Song, May 10 2021
STATUS
approved