A002475 -id:A002475 - cp's OEIS frontend

A001153 Degrees of primitive irreducible trinomials: n such that 2^n - 1 is a Mersenne prime and x^n + x^k + 1 is a primitive irreducible polynomial over GF(2) for some k with 0 < k < n.

2, 3, 5, 7, 17, 31, 89, 127, 521, 607, 1279, 2281, 3217, 4423, 9689, 19937, 23209, 44497, 110503, 132049, 756839, 859433, 3021377, 6972593, 24036583, 25964951, 30402457, 32582657, 42643801, 43112609

Offset: 1

N. J. A. Sloane

Also the list of "irreducible Mersenne trinomials" since here irreducible implies primitive.
Further terms of the form +-3 (mod 8) are unlikely, as the only possibility of an irreducible trinomial for n == +-3 (mod 8) is (by Swan's theorem) x^n+x^2+1 (and its reciprocal); see the Ciet et al. and the Swan reference. - Joerg Arndt, Jan 06 2014
The first Mersenne prime exponent not ruled out by Swan's theorem and yet not a member of this sequence is 57885161. - Gord Palameta, Jul 20 2018
74207281 is also in the sequence. - Gord Palameta, Jul 20 2018

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).

Joerg Arndt, Matters Computational (The Fxtbook), see p.850 (but note errata for statement of Swan's theorem).
Joerg Arndt, Complete list of primitive trinomials over GF(2) up to degree 400.
Joerg Arndt, Complete list of primitive trinomials over GF(2) up to degree 400 [Cached copy, with permission]
R. P. Brent, Searching for primitive trinomials (mod 2) (first, "old" page)
R. P. Brent, Searching for primitive trinomials (mod 2) (second, current page)
R. P. Brent, Trinomial Log Files and Certificates
Richard P. Brent and Paul Zimmerman, Twelve New Primitive Binary Trinomials, HAL Id : hal-01378493.
R. P. Brent, S. Larvala and P. Zimmermann, A fast algorithm for testing reducibility of trinomials ..., Math. Comp. 72 (2003), 1443-1452.
Mathieu Ciet, Jean-Jacques Quisquater, Francesco Sica, A Short Note on Irreducible Trinomials in Binary Fields, in: 23rd Symposium on Information Theory in the BENELUX, Louvain-la-Neuve, Belgium, Macq, B., Quisquater, J.-J. (eds.), pp.233-234, (May-2002).
Yoshiharu Kurita and Makoto Matsumoto, Primitive t-nomials (t=3,5) over GF(2) whose degree is a Mersenne exponent <= 44497, Math. Comp. 56 (1991), no. 194, 817-821.
A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1996; see p. 162.
Richard G. Swan, Factorization of polynomials over finite fields, Pacific Journal of Mathematics, vol.12, no.3, pp.1099-1106, (1962).
N. Zierler, Primitive trinomials whose degree is a Mersenne exponent, Information and Control 15 1969 67-69.
N. Zierler, On x^n+x+1 over GF(2), Information and Control 16 1970 502-505.
N. Zierler and J. Brillhart, On primitive trinomials (mod 2), Information and Control 13 1968 541-554.
N. Zierler and J. Brillhart, On primitive trinomials (mod 2), II, Information and Control 14 1969 566-569.
Index entries for sequences related to trinomials over GF(2)

Cf. A002475, A000043, A073571, A073639, A057486, A073726.

For smallest values of k, see A074743.

Corrected and extended by Paul Zimmermann, Sep 05 2002

Six more terms from Brent's page added by Max Alekseyev, Oct 22 2011

A223934 Least prime p such that x^n-x-1 is irreducible modulo p.

Original entry on oeis.org

2, 2, 2, 3, 2, 2, 7, 2, 17, 7, 5, 3, 3, 2, 109, 3, 101, 19, 229, 5, 2, 23, 23, 17, 107, 269, 2, 29, 2, 31, 37, 197, 107, 73, 37, 7, 59, 233, 3, 3, 7, 43, 43, 5, 2, 47, 269, 61, 43, 3, 53, 13, 3, 643, 13, 5, 151, 59, 2

Offset: 2

Zhi-Wei Sun, Mar 29 2013

nonn

Conjecture: a(n) < n*(n+3)/2 for all n>1.
Note that a(20) = 229 < 20*(20+3)/2 = 230.
The conjecture was motivated by E. S. Selmer's result that for any n>1 the polynomial x^n-x-1 is irreducible over the field of rational numbers.
We also conjecture that for every n=2,3,... there is a positive integer z not exceeding the (2n-2)-th prime such that z^n-z-1 is prime, and the Galois group of x^n-x-1 over the field of rationals is isomorphic to the symmetric group S_n.

			a(8)=7 since f(x)=x^8-x-1 is irreducible modulo 7 but reducible modulo any of 2, 3, 5, for,
   f(x)==(x^2+x+1)*(x^6+x^5+x^3+x^2+1) (mod 2),
   f(x)==(x^3+x^2-x+1)*(x^5-x^4-x^3-x^2+x-1) (mod 3),
   f(x)==(x^2-2x-2)*(x^6+2x^5+x^4+x^3-x^2-2) (mod 5).

Zhi-Wei Sun, Table of n, a(n) for n = 2..500
E. S. Selmer, On the irreducibility of certain trinomials, Math. Scand., 4 (1956) 287-302.

Cf. A000040, A220072, A217785, A217788, A218465.
Cf. A002475 (n such that x^n-x-1 is irreducible over GF(2)).
Cf. A223938 (n such that x^n-x-1 is irreducible over GF(3)).

Do[Do[If[IrreduciblePolynomialQ[x^n-x-1,Modulus->Prime[k]]==True,Print[n," ",Prime[k]];Goto[aa]],{k,1,PrimePi[n*(n+3)/2-1]}];
Print[n," ",counterexample];Label[aa];Continue,{n,2,100}]

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

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 10, 17, 20, 25, 28, 31, 41, 52, 130, 151, 196, 503, 650, 761, 986, 1391, 2047, 6172, 6431, 6730, 8425, 10162, 11410, 12071, 13151, 14636, 17377, 18023, 32770, 77047, 102842, 130777, 137113, 143503, 168812, 192076

Offset: 1

Robert G. Wilson v, Sep 27 2000

nonn

If x^n + x^3 + x^2 + x + 1 is irreducible, then so is its "twin" x^n + x^3 + 1. - Gove Effinger, Mar 11 2007

No term other than 3 can be a multiple of 3, since for m > 1, x^(3*m) + x^3 + x^2 + x + 1 is divisible by x^2 + x + 1. - Jianing Song, May 11 2021

Cf. A002475.

Other than the term 3, subsequence of A057461.

Using probabilistic arguments it appears that there should be about 6.5 terms in this sequence with any given number of decimal digits d. - Gove Effinger, Mar 11 2007

a(20)-a(23) from Robert G. Wilson v, Mar 11 2007
a(24)-a(27) computed by Richard P. Brent, Mar 11 2007, communicated by Gove Effinger
a(27)-a(35) computed by Richard P. Brent, Mar 16 2007, communicated by Gove Effinger
a(36)-a(42) computed by Jonathan Webster, Feb 18 2010
Added entries a(1), a(2), a(3) since x^3 + x^2 + 1, x^3 + x + 1 and x^2 + x + 1 are irreducible over GF(2). Changed the offset for the entries computed by Robert G. Wilson v and Richard P. Brent to account for this. Added terms a(36) through a(42). - Jonathan Webster (jwebster(AT)bates.edu), Feb 18 2010

A073639 Numbers k such that x^k + x + 1 is a primitive polynomial modulo 2.

Original entry on oeis.org

2, 3, 4, 6, 7, 15, 22, 60, 63, 127, 153, 471, 532, 865, 900, 1366

Offset: 1

Richard P. Brent and Paul Zimmermann, Sep 05 2002

Subsequence of A002475, which gives k for which the polynomial x^k + x + 1 is irreducible modulo 2. Term m of A002475 belongs to this sequence iff A046932(m) = 2^m - 1.
Note that a(16) = 1366 = A002475(23). For k = A002475(24) and A002475(25), polynomial x^k + x + 1 is not primitive modulo 2, so a(17) >= A002475(26) = 4495.
The following large terms of A002475 do not belong here: 53484, 62481, 83406, 103468. - Max Alekseyev, Aug 18 2015

Joerg Arndt, Matters Computational (The Fxtbook), section 40.9.3 "Irreducible trinomials of the form 1 + x^k + x^d", p.850
I. F. Blake, S. Gao and R. J. Lambert, Constructive problems for irreducible polynomials over finite fields, in Information Theory and Applications, LNCS 793, Springer-Verlag, Berlin, 1994, 1-23, See Table 2.
R. P. Brent, Searching for primitive trinomials (mod 2)
R. P. Brent, S. Larvala and P. Zimmermann, A fast algorithm for testing reducibility of trinomials ..., Math. Comp. 72 (2003), 1443-1452.
N. Zierler, Primitive trinomials whose degree is a Mersenne exponent, Information and Control 15 1969 67-69.
N. Zierler, On x^n+x+1 over GF(2), Information and Control 16 1970 502-505.
N. Zierler and J. Brillhart, On primitive trinomials (mod 2), Information and Control 13 1968 541-554.
N. Zierler and J. Brillhart, On primitive trinomials (mod 2), II, Information and Control 14 1969 566-569.
Index entries for sequences related to trinomials over GF(2)

Cf. A002475, A073571, A057486.

Select[Range[2, 1000], PrimitivePolynomialQ[x^# + x + 1, 2] &] (* Robert Price, Sep 19 2018 *)

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

Original entry on oeis.org

1, 3, 5, 11, 21, 29, 35, 93, 123, 333, 845, 4125, 10437, 10469, 14211, 20307, 34115, 47283, 50621, 57341, 70331, 80141

Offset: 1

Robert G. Wilson v, Sep 27 2000

Any subsequent terms are > 300000. - Lucas A. Brown, Nov 28 2022

Joerg Arndt, Matters Computational (The Fxtbook)
I. F. Blake, S. Gao and R. J. Lambert, Constructive problems for irreducible polynomials over finite fields, in Information Theory and Applications, LNCS 793, Springer-Verlag, Berlin, 1994, 1-23, See Table 2.
Lucas A. Brown, Python program.
Lucas A. Brown, Sage program.
H. Fredricksen, R. Wisniewski, On trinomials x^n + x^2 + 1 and x^{8l+-1} + x^k + 1 irreducible overGF(2), Inform. and Control 50 (1981), no. 1, 58--63. MR0665139 (84i:12013). Gives first 20 terms.
Index entries for sequences related to trinomials over GF(2)

Cf. A002475, A074710.

isok(n) = polisirreducible(Mod(1,2)*(x^n + x^2 + 1)); \\ Michel Marcus, Aug 23 2015

Confirmed by Richard P. Brent, Sep 05 2002

a(21) and a(22) from Lucas A. Brown, Nov 28 2022

A057486 Numbers k such that x^k + x^m + 1 is factorable over GF(2) for all m between 1 and k.

Original entry on oeis.org

8, 13, 16, 19, 24, 26, 27, 32, 37, 38, 40, 43, 45, 48, 50, 51, 53, 56, 59, 61, 64, 67, 69, 70, 72, 75, 77, 78, 80, 82, 83, 85, 88, 91, 96, 99, 101, 104, 107, 109, 112, 114, 115, 116, 117, 120, 122, 125, 128, 131, 133, 136, 138, 139, 141, 143, 144, 149, 152, 157

Offset: 1

Robert G. Wilson v, Sep 28 2000

nonn

Brent, Hart, Kruppa, and Zimmermann found that 57885161 is a term of this sequence. - Charles R Greathouse IV, May 30 2013

			a(1) = 8 because
x^8 + x^1 + 1 = (1 + x + x^2)*(1 + x^2 + x^3 + x^5 + x^6),
x^8 + x^2 + 1 = (1 + x + x^4)^2,
x^8 + x^3 + 1 = (1 + x + x^3)*(1 + x + x^2 + x^3 + x^5),
x^8 + x^4 + 1 = (1 + x + x^2)^4,
x^8 + x^5 + 1 = (1 + x^2 + x^3)*(1 + x^2 + x^3 + x^4 + x^5),
x^8 + x^6 + 1 = (1 + x^3 + x^4)^2, and
x^8 + x^7 + 1 = (1 + x + x^2)*(1 + x + x^3 + x^4 + x^6).

Charles R Greathouse IV, Table of n, a(n) for n = 1..5000 (first 200 terms from T. D. Noe)
Richard Brent, The Software gf2x.
Paul Zimmermann, There is no primitive trinomial of degree 57885161 over GF(2), posting to NMBRTHRY mailing list [alternate link]
Index entries for sequences related to trinomials over GF(2)

Complement of A073571. Cf. A001153, A002475, A073639.

Do[ k = 1; While[ ToString[ Factor[ x^n + x^k + 1, Modulus -> 2 ]] != ToString[ x^n + x^k + 1 ] && k < n, k++ ]; If[ k == n, Print[ n ]], {n, 2, 234} ]

is(n)=for(s=1,n\2,if(polisirreducible((x^n+x^s+1)*Mod(1,2)), return(0)));1 \\ Charles R Greathouse IV, May 30 2013

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

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

Original entry on oeis.org

1, 4, 5, 8, 11, 12, 14, 18, 23, 28, 30, 36, 49, 54, 60, 68, 71, 79, 84, 103, 113, 151, 156, 191, 198, 364, 390, 470, 476, 508, 540, 620, 721, 823, 865, 1135, 1558, 1825, 1950, 4225, 4788, 8100, 12294, 12553, 14686, 18516, 19660, 24470, 30486, 32086, 43908

Offset: 1

Robert G. Wilson v, Sep 27 2000

nonn

The b-file contains all terms <= 300000. - Lucas A. Brown, Nov 28 2022

Lucas A. Brown, Table of n, a(n) for n = 1..67
Lucas A. Brown, Python program.
Lucas A. Brown, Sage program.

Cf. A002475.

select(n  -> Irreduc(x^n + x^9 + 1) mod 2, [$1..1000]); # Robert Israel, Oct 20 2016

isok(n) = polisirreducible(Mod(1,2)*(x^n + x^9 + 1)); \\ Michel Marcus, Oct 20 2016

a(34)-a(41) from Robert Israel, Oct 20 2016
a(42) from Alois P. Heinz, Oct 20 2016
a(43)-a(67) from Lucas A. Brown, Nov 28 2022

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

Original entry on oeis.org

1, 3, 7, 9, 15, 39, 57, 81, 105, 1239, 5569, 9457, 11095, 11631, 12327, 37633, 63247, 216457

Offset: 1

Robert G. Wilson v, Sep 27 2000

a(18) is greater than 10^5. - Joerg Arndt, Apr 28 2012
All terms are congruent to 1 or 3 (mod 6). - Robert Israel, Sep 05 2016
Any subsequent terms are > 300000. - Lucas A. Brown, Nov 28 2022

			6 is not in the sequence since x^6 + x^4 + 1 = (x^3 + x^2 + 1)^2, but 7 is in the sequence since x^7 + x^4 + 1 is irreducible. (Trial division by x + 1, x^2 + x + 1, x^3 + x^2 + 1, and x^3 + x + 1) - _Michael B. Porter_, Sep 06 2016

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.

for m from 1 to 200 do if(Irreduc(x^m + x^4 + 1) mod 2) then printf("%d, ",m):fi:od: # Nathaniel Johnston, Apr 19 2011

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

a(10)-a(15) from Nathaniel Johnston, Apr 19 2011
a(16)-a(17) from Joerg Arndt, Apr 28 2012
a(18) from Lucas A. Brown, Nov 28 2022

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

Original entry on oeis.org

1, 3, 5, 7, 17, 31, 71, 97, 167, 175, 209, 385, 2159, 5617, 8921, 33425, 39119, 76625, 110249, 192127, 255265

Offset: 1

Robert G. Wilson v, Sep 27 2000

a(16) > 30000 if it exists. - Robert Israel, Nov 11 2016

Any subsequent terms are > 300000. - Lucas A. Brown, Nov 28 2022

Lucas A. Brown, Python program.
Lucas A. Brown, Sage program.

Cf. A002475.

select(n -> Irreduc(x^n+x^6+1) mod 2, [$1..1000]); # Robert Israel, Nov 11 2016

a(13)-a(15) from Robert Israel, Nov 11 2016

a(16)-a(21) from Lucas A. Brown, Nov 28 2022

cp's OEIS Frontend

A001153 Degrees of primitive irreducible trinomials: n such that 2^n - 1 is a Mersenne prime and x^n + x^k + 1 is a primitive irreducible polynomial over GF(2) for some k with 0 < k < n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A223934 Least prime p such that x^n-x-1 is irreducible modulo p.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Crossrefs

Formula

Extensions

A073639 Numbers k such that x^k + x + 1 is a primitive polynomial modulo 2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Extensions

A057486 Numbers k such that x^k + x^m + 1 is factorable over GF(2) for all m between 1 and k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

PARI

Extensions