

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
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



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

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).


KEYWORD

easy,nonn


AUTHOR



EXTENSIONS



STATUS

approved



