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

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

Offset

1,3

Comments

All such polynomials of odd degree > 1 are reducible over GF(2).

For n >= 2, a(n) = A001122(n-2) - 1 due to the relationship between cycles and irreducibility. - T. D. Noe, Sep 09 2003

n such that a type-1 optimal normal basis of GF(2^n) (over GF(2)) exists. The corresponding field polynomial is the all-ones polynomial x^n+x^(n-1)+...+1. - Joerg Arndt, Feb 25 2008

From Peter R. J. Asveld, Aug 13 2009: (Start)

a(n) is also the n-th S-prime (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 S-prime if p(m,N) consists of a single cycle of length N.

So all S-primes are even.

N is S-prime 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_2-primes (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 Twist-primes or Queneau numbers (A054639); their intersection is equal to the Archimedes_0-primes (A163777). (End)

Conjecture: Terms >= 2 are numbers n such that P^n + P^(n-1) + P^(n-2) + ... + 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.914-920

P. R. J. Asveld, Permuting operations on strings and their relation to prime numbers, Discrete Applied Mathematics 159 (2011) 1915-1932.

P. R. J. Asveld, Permuting operations on strings and the distribution of their prime numbers, (2011), TR-CTIT-11-24, Dept. of CS, Twente University of Technology, Enschede, The Netherlands.

P. R. J. Asveld, Some Families of Permutations and Their Primes (2009), TR-CTIT-09-27, Dept. of CS, Twente University of Technology, Enschede, The Netherlands.

P. R. J. Asveld, Permuting Operations on Strings-Their Permutations and Their Primes, Twente University of Technology, 2014.

Hélianthe Caure, Canons rythmiques et pavages modulaires, Thesis Université Pierre et Marie Curie - Paris VI, 2016. See page 108. In French.

H. Caure, C. Agon, and M. Andreatta, Modulus p Rhythmic Tiling Canons and some implementations in Open Music visual programming language, in Proceedings ICMC|SMC|2014 14-20 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 S-prime, 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] == p-1, Sow[p-1]]]][[2, 1]]] (* Jean-François Alcover, Dec 10 2015, adapted from PARI *)

Prog

(PARI) forprime(p=3, 1000, if(znorder(Mod(2, p))==p-1, print1(p-1, ", "))) /* 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 b-file corrected by N. J. A. Sloane, Aug 31 2009

Status

approved