A073726 Primitive irreducible trinomials: x^n + x^k + 1 is a primitive irreducible polynomial (mod 2) for some k with 0 < k < n.

2, 3, 4, 5, 6, 7, 9, 10, 11, 15, 17, 18, 20, 21, 22, 23, 25, 28, 29, 31, 33, 35, 36, 39, 41, 47, 49, 52, 55, 57, 58, 60, 63, 65, 68, 71, 73, 79, 81, 84, 87, 89, 93, 94, 95, 97, 98, 100, 103, 105, 106, 108, 111, 113, 118, 119, 121, 123, 124, 127, 129, 130, 132, 134, 135, 137, 140, 142, 145, 148, 150, 151, 153, 159, 161, 167, 169, 170, 172, 174, 175, 177, 178, 183, 185, 191, 193, 194, 198, 199, 201

Offset: 1

Author

Richard P. Brent and Paul Zimmermann, Sep 05 2002

Keywords

• nonn
• nice

Comments

Start is similar to A194125; first terms here but missing there are 140, 212, 236.

References

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

Links

• 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]
• A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1996; see Table 4.8.
• Index entries for sequences related to trinomials over GF(2)

Crossrefs

See A073571 for irreducible trinomials and A001153 for primitive Mersenne trinomials (and references). See A074744 for values of k.

Cf. A194125 (n such that x^n+(1+x)^w over GF(2) is primitive for some w).

Programs

Magma

A073726 := function(n) for k := 1 to n-1 do if IsPrimitive(x^n+x^k+1) then return true; end if; end for; return false; end function; l := []; for n := 1 to 100 do if A073726(n) then l := Append(l,n); end if; end for; l;

Maple

A073726 := proc(n) local k,m: option remember: if(n=1)then return 2: else m:=procname(n-1)+1: while(true)do for k from 1 to m-1 do if Primitive(x^m+x^k+1) mod 2 then return m: fi: od: m:=m+1: od: fi: end:
seq(A073726(n),n=1..20); # Nathaniel Johnston, Apr 26 2011

Mathematica

okQ[n_] := AnyTrue[Range[n-1], PrimitivePolynomialQ[x^n + x^# + 1, 2]&];
Select[Range[201], okQ] (* Jean-François Alcover, Aug 19 2019 *)

Extensions

a(49)-a(58) from Nathaniel Johnston, Apr 26 2011