A057496 -id:A057496 - cp's OEIS frontend

A002475 Numbers k such that x^k + x + 1 is irreducible over GF(2).

0, 2, 3, 4, 6, 7, 9, 15, 22, 28, 30, 46, 60, 63, 127, 153, 172, 303, 471, 532, 865, 900, 1366, 2380, 3310, 4495, 6321, 7447, 10198, 11425, 21846, 24369, 27286, 28713, 32767, 34353, 46383, 53484, 62481, 83406, 87382, 103468, 198958, 248833

Offset: 1

N. J. A. Sloane

k=1 is excluded since the polynomial "1" is not normally regarded as irreducible.
2^(A073639(m)) - 1 is a term for all m. - Joerg Arndt, Aug 23 2015
Any subsequent terms are > 300000. - Lucas A. Brown, Nov 28 2022

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Stephen Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 975.

Joerg Arndt, Matters Computational (The Fxtbook), section 40.9.3 "Irreducible trinomials of the form 1 + x^k + x^d", p.850
Lucas A. Brown, Python program.
Lucas A. Brown, Sage program.
N. Zierler, On x^n+x+1 over GF(2), Information and Control, 16 1970 502-505.
Index entries for sequences related to trinomials over GF(2)

Cf. A001153, A073639, A057496, A223938 (n such that x^n-x-1 is irreducible over GF(3)).

P := PolynomialRing(GaloisField(2)); for n := 0 to 100000 do if IsIrreducible(x^n+x+1) then print(n); end if; end for;

select(n -> Irreduc(x^n+x+1) mod 2, [0,$2..10000]); # Robert Israel, Aug 09 2015

Do[ If[ ToString[ Factor[ x^n + x + 1, Modulus -> 2 ] ] == ToString[ x^n + x + 1 ], Print [ n ] ], {n, 0, 28713} ]
Select[Range[1000], IrreduciblePolynomialQ[x^# + x + 1, Modulus -> 2] &] (* Robert Price, Sep 19 2018 *)

for (n=1,10^6, if ( polisirreducible(Mod(1,2)*(x^n+x+1)), print1(n,", ") ) );
/* Joerg Arndt, Apr 28 2012 */

is(n)=if(n>3&&[1,0,1,1,0,1,0,0][n%8+1], return(0)); polisirreducible(Mod('x^n+'x+1,2)) \\ Charles R Greathouse IV, Jun 04 2015

P. = GF(2)[]
for n in range(90):
       if (x^n+x+1).is_irreducible():
           print(n) # Ruperto Corso, Dec 11 2011

Two more terms from Paul Zimmermann, Sep 05 2002
a(37)-a(39) from Max Alekseyev, Oct 29 2011
a(40)-a(41) from Ruperto Corso, Dec 11 2011
a(42) from Manfred Scheucher, Jun 04 2015
a(43) from Manfred Scheucher, Aug 09 2015
a(44) from Lucas A. Brown, Nov 28 2022

A344177 Numbers m > 3 such that x^m + x^3 + 1 is irreducible over GF(2) while x^m + x^3 + x^2 + x + 1 = x^m + (x + 1)^3 is not.

Original entry on oeis.org

6, 12, 18, 66, 180, 1596, 2700, 4098, 30594, 65538

Offset: 1

Jianing Song, May 11 2021

Numbers m >= 4 that are in A057461 but not in A057496.
In A057496 it is stated that if x^m + x^3 + x^2 + x + 1 is irreducible, then so is x^m + x^3 + 1. It seems that if x^m + x^3 + 1 is irreducible and m is not a multiple of 6, then so is x^m + x^3 + x^2 + x + 1. In other words, it seems that this sequence consists of the terms in A057461 that are multiples of 6.
Conjecture: Given e >= 0, odd numbers r, k > 0, a > 2^e*r*k, consider the following two statements:
(A) x^m + (x^k + 1)^(2^e*r) is irreducible over GF(2);
(B) x^m + x^(2^e*r*k) + 1 is irreducible over GF(2),
then:
(i) (A) implies (B);
(ii) if (B) is true and (A) is false, then:
    (a) gcd(m,r) > 1;
    (b) if prime p | gcd(m,r*k), then p*ord_p(2) | m;
    (c) if e > 0, then m is odd.
Here ord(2,p) is the multiplicative order of 2 modulo p.
In other words, assuming that (B) is true, (A) is false if and only if (a), (b), (c) hold. (For the "if" part, note that if d = gcd(m,2^e*r) > 1 then x^m + (x^k + 1)^(2^e*r) must be reducible, since it is divisible by x^(m/d) + (x^k + 1)^(2^e*r/d).)
Here is the case r = 3, k = 1, e = 0, and (ii) means that m is in this sequence if and only if x^m + x^3 + 1 is irreducible and m is a multiple of 6.

			18 is a term because x^18 + x^3 + 1 is irreducible over GF(2) but x^18 + x^3 + x^2 + x + 1 is not: x^18 + x^3 + x^2 + x + 1 = (x^2 + x + 1)*(x^6 + x + 1)*(x^10 + x^9 + x^7 + x^6 + x^5 + x^4 + x^2 + x + 1).

Cf. A057461, A057496.

Similar sequences: this sequence (r=3, k=1), A344198 (r=3, k=3), A344199 (r=3, k=5), A344197 (r=5, k=1), A344200 (r=5, k=3).

isA344177(n) = polisirreducible(Mod(x^n+x^3+1, 2)) && !polisirreducible(Mod(x^n+x^3+x^2+x+1, 2))

A057461 Numbers k such that x^k + x^3 + 1 is irreducible over GF(2).

Original entry on oeis.org

1, 2, 4, 5, 6, 7, 10, 12, 17, 18, 20, 25, 28, 31, 41, 52, 66, 130, 151, 180, 196, 503, 650, 761, 986, 1391, 1596, 2047, 2700, 4098, 6172, 6431, 6730, 8425, 10162, 11410, 12071, 13151, 14636, 17377, 18023, 30594, 32770, 65538, 77047, 81858, 102842, 130777, 137113, 143503, 168812, 192076, 262146

Offset: 1

Robert G. Wilson v, Sep 27 2000

Next term is > 10^5. - Joerg Arndt, Apr 28 2012
It seems that if x^k + x^3 + 1 is irreducible and k is not a multiple of 6, then so is x^k + x^3 + x^2 + x + 1. If this is true, then no term can be congruent to 3 modulo 6. - Jianing Song, May 11 2021
Any subsequent terms are > 300000. - Lucas A. Brown, Nov 28 2022

Joerg Arndt, Matters Computational (The Fxtbook), section 40.9.3 "Irreducible trinomials of the form 1 + x^k + x^d", p. 850
Lucas A. Brown, Python program.
Lucas A. Brown, Sage program.

Cf. A002475, A057496.

for (n=1,5000, if ( polisirreducible(Mod(1,2)*(x^n+x^3+1)), print1(n,", ") ) );
/* Joerg Arndt, Apr 28 2012 */

P. = GF(2)[]
for n in range(10^4):
    if (x^n+x^3+1).is_irreducible():
        print(n) # Joerg Arndt, Apr 28 2012

a(24)-a(29) from Robert G. Wilson v, Aug 06 2010
Terms >= 4098 from Joerg Arndt, Apr 28 2012
a(47)-a(53) from Lucas A. Brown, Nov 28 2022

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

Original entry on oeis.org

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

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

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.

A344185 a(n) = A344141(n) - 2^n.

Original entry on oeis.org

0, 3, 3, 3, 5, 3, 3, 27, 3, 9, 5, 9, 27, 33, 3, 43, 9, 9, 39, 9, 5, 3, 33, 27, 9, 27, 39, 3, 5, 3, 9, 141, 75, 27, 5, 53, 63, 99, 17, 57, 9, 39, 89, 33, 27, 3, 33, 45, 113, 29, 75, 9, 71, 125, 71, 149, 17, 99, 123, 3, 39, 105, 3, 27, 27, 9, 39, 163, 101, 43

Offset: 1

Jianing Song, May 11 2021

nonn

A more intuitive version of A344141.
Every term other than the first is a member of A129771.
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 can be equal to 15.
It is conjectured that no term can be of the form P_m(2^k), where P_m(x) = Product_{i>=0} (1 + x^(2^(d_i)))^(c_i) if the binary representation of m is m = Sum_{i>=0} c_i * 2^(d_i), k is an odd number. See my conjecture in A344177.

			See A344141.

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

Cf. A014580, A344141, A344186, A129771, A344177.

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

A344186 a(n) = A344142(n) - 2^n.

Original entry on oeis.org

0, 3, 3, 3, 5, 3, 3, 27, 3, 9, 5, 9, 27, 33, 3, 43, 9, 9, 39, 9, 5, 3, 33, 27, 9, 27, 39, 3, 5, 3, 9, 141, 1025, 129, 5, 513, 83, 99, 17, 57, 9, 129, 89, 33, 27, 3, 33, 45, 513, 29, 75, 9, 71, 513, 129, 149, 17, 524289, 149, 3, 39, 536870913, 3, 27, 262145, 9, 39, 513, 101, 43

Offset: 1

Jianing Song, May 11 2021

nonn

A more intuitive version of A344142.
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 can be equal to 15.
It is conjectured that an irreducible polynomial of degree n with 5 terms exists for every n. It follows from the conjecture that for n >= 2, a(n) is of the form 2^k + 1 or an odd number with Hamming weight 4.
It is conjectured that no term can be of the form P_m(2^k), where P_m(x) = Product_{i>=0} (1 + x^(2^(d_i)))^(c_i) if the binary representation of m is m = Sum_{i>=0} c_i * 2^(d_i), k is an odd number. See my conjecture in A344177.

			See A344142.

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

Cf. A014580, A344142, A344185, A344177.

A344186(n) = if(n==1, 0, for(k=1, n-1, if(polisirreducible(Mod(x^n+x^k+1, 2)), return(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^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

A002475 Numbers k such that x^k + x + 1 is irreducible over GF(2).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

SageMath

Extensions

A344177 Numbers m > 3 such that x^m + x^3 + 1 is irreducible over GF(2) while x^m + x^3 + x^2 + x + 1 = x^m + (x + 1)^3 is not.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

A057461 Numbers k such that x^k + x^3 + 1 is irreducible over GF(2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Sage

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A344185 a(n) = A344141(n) - 2^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A344186 a(n) = A344142(n) - 2^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI