A073571 Irreducible trinomials: numbers n such that x^n + x^k + 1 is an irreducible polynomial (mod 2) for some k with 0 < k < n.

2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 14, 15, 17, 18, 20, 21, 22, 23, 25, 28, 29, 30, 31, 33, 34, 35, 36, 39, 41, 42, 44, 46, 47, 49, 52, 54, 55, 57, 58, 60, 62, 63, 65, 66, 68, 71, 73, 74, 76, 79, 81, 84, 86, 87, 89, 90, 92, 93, 94, 95, 97, 98, 100, 102, 103, 105, 106, 108, 110, 111, 113

Offset: 1

Author

Paul Zimmermann, Sep 05 2002

Keywords

• nonn

Comments

This sequence is infinite: Golomb, "Shift Register Sequences," on p. 96 (1st ed., 1966) states that "It is easy to exhibit an infinite class of irreducible trinomials. viz. x^(2*3^a) + x^(3^a) + 1 for all a = 0, 1, 2, ..., but whose roots have only 3^(a+1) as their period." - A. M. Odlyzko, Dec 05 1997.

References

• S. W. Golomb, "Shift register sequence", revised edition, reprinted by Aegean Park Press, 1982. See Tables V-1, V-2.

Links

• Joerg Arndt, Table of n, a(n) for n = 1..1500
• A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1996; see Table 4.6.
• Index entries for sequences related to trinomials over GF(2)

Crossrefs

For the numbers of such trinomials for a given n, see A057646.

See A073726 for primitive trinomials and A001153 for primitive Mersenne trinomials (and references). Complement of A057486. For values of k see A057774.

Programs

Maple

a := proc(n) local k; for k from 1 to n-1 do if Irreduc(x^n+x^k+1) mod 2 then RETURN(n) fi od; NULL end: [seq(a(n), n=1..130)];

Mathematica

irreducibleQ[n_] := (irr = False; k = 1; While[k < n, If[ Factor[ x^n + x^k + 1, Modulus -> 2] == x^n + x^k + 1, irr = True; Break[]]; k++]; irr); Select[ Range[120], irreducibleQ] (* Jean-François Alcover, Jan 07 2013 *)

PARI

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