cp's OEIS Frontend

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

%I A073726 #41 Dec 17 2024 18:30:44
%S A073726 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,
%T A073726 47,49,52,55,57,58,60,63,65,68,71,73,79,81,84,87,89,93,94,95,97,98,
%U A073726 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
%N A073726 Primitive irreducible trinomials: x^n + x^k + 1 is a primitive irreducible polynomial (mod 2) for some k with 0 < k < n.
%C A073726 Start is similar to A194125; first terms here but missing there are 140, 212, 236.
%D A073726 S. W. Golomb, "Shift Register Sequences", revised edition, reprinted by Aegean Park Press, 1982. See Tables V-1, V-2.
%H A073726 Joerg Arndt, <a href="http://www.jjj.de/mathdata/all-trinomial-primpoly.txt">Complete list of primitive trinomials over GF(2) up to degree 400</a>.
%H A073726 Joerg Arndt, <a href="/A001153/a001153.txt">Complete list of primitive trinomials over GF(2) up to degree 400</a> [Cached copy, with permission]
%H A073726 A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, <a href="https://cacr.uwaterloo.ca/hac/">Handbook of Applied Cryptography</a>, CRC Press, 1996; see Table 4.8.
%H A073726 <a href="/index/Tri#trinomial">Index entries for sequences related to trinomials over GF(2)</a>
%p A073726 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:
%p A073726 seq(A073726(n),n=1..20); # _Nathaniel Johnston_, Apr 26 2011
%t A073726 okQ[n_] := AnyTrue[Range[n-1], PrimitivePolynomialQ[x^n + x^# + 1, 2]&];
%t A073726 Select[Range[201], okQ] (* _Jean-François Alcover_, Aug 19 2019 *)
%o A073726 (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;
%Y A073726 See A073571 for irreducible trinomials and A001153 for primitive Mersenne trinomials (and references). See A074744 for values of k.
%Y A073726 Cf. A194125 (n such that x^n+(1+x)^w over GF(2) is primitive for some w).
%K A073726 nonn,nice
%O A073726 1,1
%A A073726 _Richard P. Brent_ and _Paul Zimmermann_, Sep 05 2002
%E A073726 a(49)-a(58) from _Nathaniel Johnston_, Apr 26 2011