

A071642


Numbers n such that x^n + x^(n1) + x^(n2) + ... + x + 1 is irreducible over GF(2).


18



0, 1, 2, 4, 10, 12, 18, 28, 36, 52, 58, 60, 66, 82, 100, 106, 130, 138, 148, 162, 172, 178, 180, 196, 210, 226, 268, 292, 316, 346, 348, 372, 378, 388, 418, 420, 442, 460, 466, 490, 508, 522, 540, 546, 556, 562, 586, 612, 618, 652, 658, 660, 676, 700, 708, 756, 772
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

All such polynomials of odd degree > 1 are reducible over GF(2).
For n >= 2, a(n) = A001122(n2)  1 due to the relationship between cycles and irreducibility.  T. D. Noe, Sep 09 2003
n such that a type1 optimal normal basis of GF(2^n) (over GF(2)) exists. The corresponding field polynomial is the allones polynomial x^n+x^(n1)+...+1.  Joerg Arndt, Feb 25 2008
From Peter R. J. Asveld, Aug 13 2009: (Start)
a(n) is also the nth Sprime (Shuffle prime)
For N>=2, the family of shuffle permutations is defined by
p(m,N) = 2m (mod N+1) if N is even,
p(m,N) = 2m (mod N) if N is odd and 1<=m<N,
p(N,N) = N if N is odd.
N is Sprime if p(m,N) consists of a single cycle of length N.
So all Sprimes are even.
N is Sprime iff p=N+1 is an odd prime number and +2 generates Z_p^* (the multiplicative group of Z_p).
a(n)/2 results in the Josephus_2primes (A163782). Considered as sets a(n)/2 is the union of A163777 and A163779. If b(n) denotes the dual shuffle primes (A163776), then the union of a(n)/2 and b(n)/2 is equal to the Twistprimes or Queneau numbers (A054639); their intersection is equal to the Archimedes_0primes (A163777). (End)
Conjecture: Terms >= 2 are numbers n such that P^n + P^(n1) + P^(n2) + ... + P + 1 is irreducible over GF(2), where P=x^2+x+1.  Luis H. Gallardo, Dec 23 2019


LINKS

P. R. J. Asveld, Table of n, a(n) for n = 1..3605
Joerg Arndt, Matters Computational (The Fxtbook), section 42.9 "Gaussian normal bases", pp.914920
P. R. J. Asveld, Permuting operations on strings and their relation to prime numbers, Discrete Applied Mathematics 159 (2011) 19151932.
P. R. J. Asveld, Permuting operations on strings and the distribution of their prime numbers, (2011), TRCTIT1124, Dept. of CS, Twente University of Technology, Enschede, The Netherlands.
P. R. J. Asveld, Some Families of Permutations and Their Primes (2009), TRCTIT0927, Dept. of CS, Twente University of Technology, Enschede, The Netherlands.
P. R. J. Asveld, Permuting Operations on StringsTheir Permutations and Their Primes, Twente University of Technology, 2014.
H. Caure, C. Agon, M. Andreatta, Modulus p Rhythmic Tiling Canons and some implementations in Open Music visual programming language, in Proceedings ICMCSMC2014 1420 September 2014, Athens, Greece.
M. Olofsson, VLSI Aspects on Inversion in Finite Fields, Dissertation No. 731, Dept. Elect. Engin., Linkoping, Sweden, 2002.
Eric Weisstein's World of Mathematics, Irreducible Polynomial
Index entries for sequences related to the Josephus Problem


EXAMPLE

For n=4 and n=6 we obtain the permutations (1 2 4 3) and (1 2 4)(3 6 5): 4 is Sprime, but 6 is not. [Peter R. J. Asveld, Aug 13 2009]


MATHEMATICA

Do[s = Sum[x^i, {i, 0, n}]; If[ ToString[ Factor[s, Modulus > 2]] == ToString[s], Print[n]], {n, 2, 1000, 2}]
Join[{0, 1}, Reap[For[p = 2, p < 10^3, p = NextPrime[p], If[ MultiplicativeOrder[2, p] == p1, Sow[p1]]]][[2, 1]]] (* JeanFrançois Alcover, Dec 10 2015, adapted from PARI *)


PROG

(PARI) forprime(p=3, 1000, if(znorder(Mod(2, p))==p1, print1(p1, ", "))) /* Joerg Arndt, Jul 05 2011 */


CROSSREFS

Cf. A001122 (primes with primitive root 2).
Sequence in context: A047463 A107059 A160716 * A226827 A266538 A265223
Adjacent sequences: A071639 A071640 A071641 * A071643 A071644 A071645


KEYWORD

easy,nonn


AUTHOR

N. J. A. Sloane, Jun 22 2002


EXTENSIONS

Extended by Robert G. Wilson v, Jun 24 2002
Initial terms of bfile corrected by N. J. A. Sloane, Aug 31 2009


STATUS

approved



