

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.


9



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


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 V1, V2.


LINKS

Table of n, a(n) for n=1..71.
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)


MAPLE

a := proc(n) local k; for k from 1 to n1 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] (* JeanFrançois Alcover, Jan 07 2013 *)


PROG

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


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.
Sequence in context: A026470 A014133 A070115 * A191852 A136416 A072497
Adjacent sequences: A073568 A073569 A073570 * A073572 A073573 A073574


KEYWORD

nonn


AUTHOR

Paul Zimmermann, Sep 05 2002


STATUS

approved



