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

%I #85 Feb 29 2024 06:26:56

%S 0,1,2,4,10,12,18,28,36,52,58,60,66,82,100,106,130,138,148,162,172,

%T 178,180,196,210,226,268,292,316,346,348,372,378,388,418,420,442,460,

%U 466,490,508,522,540,546,556,562,586,612,618,652,658,660,676,700,708,756,772

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

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

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

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

%C From _Peter R. J. Asveld_, Aug 13 2009: (Start)

%C a(n) is also the n-th S-prime (Shuffle prime)

%C For N>=2, the family of shuffle permutations is defined by

%C p(m,N) = 2m (mod N+1) if N is even,

%C p(m,N) = 2m (mod N) if N is odd and 1<=m<N,

%C p(N,N) = N if N is odd.

%C N is S-prime if p(m,N) consists of a single cycle of length N.

%C So all S-primes are even.

%C N is S-prime iff p=N+1 is an odd prime number and +2 generates Z_p^* (the multiplicative group of Z_p).

%C 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)

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

%H P. R. J. Asveld, <a href="/A071642/b071642.txt">Table of n, a(n) for n = 1..3605</a>

%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, section 42.9 "Gaussian normal bases", pp.914-920

%H P. R. J. Asveld, <a href="http://dx.doi.org/10.1016/j.dam.2011.07.019">Permuting operations on strings and their relation to prime numbers</a>, Discrete Applied Mathematics 159 (2011) 1915-1932.

%H P. R. J. Asveld, <a href="http://eprints.eemcs.utwente.nl/20685">Permuting operations on strings and the distribution of their prime numbers</a>, (2011), TR-CTIT-11-24, Dept. of CS, Twente University of Technology, Enschede, The Netherlands.

%H P. R. J. Asveld, <a href="http://eprints.eemcs.utwente.nl/15678/">Some Families of Permutations and Their Primes </a> (2009), TR-CTIT-09-27, Dept. of CS, Twente University of Technology, Enschede, The Netherlands.

%H P. R. J. Asveld, <a href="http://purl.utwente.nl/publications/67513">Permuting Operations on Strings-Their Permutations and Their Primes</a>, Twente University of Technology, 2014.

%H Hélianthe Caure, <a href="https://theses.hal.science/tel-01338353">Canons rythmiques et pavages modulaires</a>, Thesis Université Pierre et Marie Curie - Paris VI, 2016. See page 108. In French.

%H H. Caure, C. Agon, and M. Andreatta, <a href="http://architexte.ircam.fr/textes/Caure14a/index.pdf">Modulus p Rhythmic Tiling Canons and some implementations in Open Music visual programming language</a>, in Proceedings ICMC|SMC|2014 14-20 September 2014, Athens, Greece.

%H M. Olofsson, <a href="http://www.commsys.isy.liu.se/publications/Theses/Theses%3AMikael%3A1012402388.25.pdf">VLSI Aspects on Inversion in Finite Fields</a>, Dissertation No. 731, Dept. Elect. Engin., Linkoping, Sweden, 2002.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/IrreduciblePolynomial.html">Irreducible Polynomial</a>

%H <a href="/index/J#Josephus">Index entries for sequences related to the Josephus Problem</a>

%e 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]

%t 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 *)

%o (PARI) forprime(p=3,1000,if(znorder(Mod(2,p))==p-1,print1(p-1,", "))) /* _Joerg Arndt_, Jul 05 2011 */

%Y Cf. A001122 (primes with primitive root 2).

%K easy,nonn

%O 1,3

%A _N. J. A. Sloane_, Jun 22 2002

%E Extended by _Robert G. Wilson v_, Jun 24 2002

%E Initial terms of b-file corrected by _N. J. A. Sloane_, Aug 31 2009