

A073639


Numbers n such that x^n + x + 1 is a primitive polynomial modulo 2.


6



2, 3, 4, 6, 7, 15, 22, 60, 63, 127, 153, 471, 532, 865, 900, 1366
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

Subsequence of A002475 that gives n for which the polynomial x^n + x + 1 is irreducible modulo 2. Term m of A002475 belongs to this sequence iff A046932(m)=2^m1.
Note that a(16) = 1366 = A002475(23). For n = A002475(24) and A002475(25), polynomial x^n + x + 1 is not primitive modulo 2, so a(17) >= A002475(26) = 4495.
The following large terms of A002475 do not belong here: 53484, 62481, 83406, 103468.  Max Alekseyev, Aug 18 2015


LINKS

Table of n, a(n) for n=1..16.
Joerg Arndt, Matters Computational (The Fxtbook), section 40.9.3 "Irreducible trinomials of the form 1 + x^k + x^d", p.850
I. F. Blake, S. Gao and R. J. Lambert, Constructive problems for irreducible polynomials over finite fields, in Information Theory and Applications, LNCS 793, SpringerVerlag, Berlin, 1994, 123, See Table 2.
R. P. Brent, Searching for primitive trinomials (mod 2)
R. P. Brent, S. Larvala and P. Zimmermann, A fast algorithm for testing reducibility of trinomials ..., Math. Comp. 72 (2003), 14431452.
N. Zierler, Primitive trinomials whose degree is a Mersenne exponent, Information and Control 15 1969 6769.
N. Zierler, On x^n+x+1 over GF(2), Information and Control 16 1970 502505.
N. Zierler and J. Brillhart, On primitive trinomials (mod 2), Information and Control 13 1968 541554.
N. Zierler and J. Brillhart, On primitive trinomials (mod 2), II, Information and Control 14 1969 566569.
Index entries for sequences related to trinomials over GF(2)


MATHEMATICA

Select[Range[2, 1000], PrimitivePolynomialQ[x^# + x + 1, 2] &] (* Robert Price, Sep 19 2018 *)


CROSSREFS

Cf. A002475, A073571, A057486.
Sequence in context: A039059 A151892 A162570 * A130776 A077292 A270475
Adjacent sequences: A073636 A073637 A073638 * A073640 A073641 A073642


KEYWORD

nonn,nice,hard,more


AUTHOR

Richard P. Brent and Paul Zimmermann, Sep 05 2002


STATUS

approved



