|
%I #15 Apr 29 2019 11:38:33
%S 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,
%T 35,36,39,41,42,44,46,47,49,52,54,55,57,58,60,62,63,65,66,68,71,73,74,
%U 76,79,81,84,86,87,89,90,92,93,94,95,97,98,100,102,103,105,106,108,110,111,113
%N Irreducible trinomials: numbers n such that x^n + x^k + 1 is an irreducible polynomial (mod 2) for some k with 0 < k < n.
%C 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.
%D S. W. Golomb, "Shift register sequence", revised edition, reprinted by Aegean Park Press, 1982. See Tables V-1, V-2.
%H Joerg Arndt, <a href="/A073571/b073571.txt">Table of n, a(n) for n = 1..1500</a>
%H A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, <a href="http://www.cacr.math.uwaterloo.ca/hac/">Handbook of Applied Cryptography</a>, CRC Press, 1996; see Table 4.6.
%H <a href="/index/Tri#trinomial">Index entries for sequences related to trinomials over GF(2)</a>
%p 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)];
%t 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 *)
%o (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
%Y For the numbers of such trinomials for a given n, see A057646.
%Y See A073726 for primitive trinomials and A001153 for primitive Mersenne trinomials (and references). Complement of A057486. For values of k see A057774.
%K nonn
%O 1,1
%A _Paul Zimmermann_, Sep 05 2002
|
