cp's OEIS Frontend

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

%I A071642 #86 Feb 16 2025 08:32:46
%S A071642 0,1,2,4,10,12,18,28,36,52,58,60,66,82,100,106,130,138,148,162,172,
%T A071642 178,180,196,210,226,268,292,316,346,348,372,378,388,418,420,442,460,
%U A071642 466,490,508,522,540,546,556,562,586,612,618,652,658,660,676,700,708,756,772
%N A071642 Numbers n such that x^n + x^(n-1) + x^(n-2) + ... + x + 1 is irreducible over GF(2).
%C A071642 All such polynomials of odd degree > 1 are reducible over GF(2).
%C A071642 For n >= 2, a(n) = A001122(n-2) - 1 due to the relationship between cycles and irreducibility. - _T. D. Noe_, Sep 09 2003
%C A071642 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 A071642 From _Peter R. J. Asveld_, Aug 13 2009: (Start)
%C A071642 a(n) is also the n-th S-prime (Shuffle prime)
%C A071642 For N>=2, the family of shuffle permutations is defined by
%C A071642 p(m,N) = 2m (mod N+1) if N is even,
%C A071642 p(m,N) = 2m (mod N) if N is odd and 1<=m<N,
%C A071642 p(N,N) = N if N is odd.
%C A071642 N is S-prime if p(m,N) consists of a single cycle of length N.
%C A071642 So all S-primes are even.
%C A071642 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 A071642 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 A071642 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 A071642 P. R. J. Asveld, <a href="/A071642/b071642.txt">Table of n, a(n) for n = 1..3605</a>
%H A071642 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 A071642 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 A071642 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 A071642 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 A071642 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 A071642 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 A071642 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 A071642 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 A071642 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/IrreduciblePolynomial.html">Irreducible Polynomial</a>
%H A071642 <a href="/index/J#Josephus">Index entries for sequences related to the Josephus Problem</a>
%e A071642 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 A071642 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 A071642 (PARI) forprime(p=3,1000,if(znorder(Mod(2,p))==p-1,print1(p-1,", "))) /* _Joerg Arndt_, Jul 05 2011 */
%Y A071642 Cf. A001122 (primes with primitive root 2).
%K A071642 easy,nonn
%O A071642 1,3
%A A071642 _N. J. A. Sloane_, Jun 22 2002
%E A071642 Extended by _Robert G. Wilson v_, Jun 24 2002
%E A071642 Initial terms of b-file corrected by _N. J. A. Sloane_, Aug 31 2009