A071642 -id:A071642 - cp's OEIS frontend

A001122 Primes with primitive root 2.

3, 5, 11, 13, 19, 29, 37, 53, 59, 61, 67, 83, 101, 107, 131, 139, 149, 163, 173, 179, 181, 197, 211, 227, 269, 293, 317, 347, 349, 373, 379, 389, 419, 421, 443, 461, 467, 491, 509, 523, 541, 547, 557, 563, 587, 613, 619, 653, 659, 661, 677, 701, 709, 757, 773, 787, 797

Offset: 1

N. J. A. Sloane

Artin conjectured that this sequence is infinite.
Conjecture: sequence contains infinitely many pairs of twin primes. - Benoit Cloitre, May 08 2003
Pieter Moree writes (Oct 20 2004): Assuming the Generalized Riemann Hypothesis, it can be shown that the density of primes p such that a prescribed integer g has order (p-1)/t, with t fixed, exists and, moreover, it can be computed. This density will be a rational number times the so-called Artin constant. For 2 and 10 the density of primitive roots is A, the Artin constant itself.
It seems that this sequence consists of A050229 \ {1,2}.
Primes p such that 1/p, when written in base 2, has period p-1, which is the greatest period possible for any integer.
Positive integer 2*m-1 is in the sequence iff A179382(m)=m-1. - Vladimir Shevelev, Jul 14 2010
These are the odd primes p for which the polynomial 1+x+x^2+...+x^(p-1) is irreducible over GF(2). - V. Raman, Sep 17 2012 [Corrected by N. J. A. Sloane, Oct 17 2012]
Prime(n) is in the sequence if (and conjecturally only if) A133954(n) = prime(n). - Vladimir Shevelev, Aug 30 2013
Pollack shows that, on the GRH, that there is some C such that a(n+1) - a(n) < C infinitely often (in fact, 1 can be replaced by any positive integer). Further, for any m, a(n), a(n+1), ..., a(n+m) are consecutive primes infinitely often. - Charles R Greathouse IV, Jan 05 2015
From Jianing Song, Apr 27 2019: (Start)
All terms are congruent to 3 or 5 modulo 8. If we define
  Pi(N,b) = # {p prime, p <= N, p == b (mod 8)};
     Q(N) = # {p prime, p <= N, p in this sequence},
then by Artin's conjecture, Q(N) ~ C*N/log(N) ~ 2*C*(Pi(N,3) + Pi(N,5)), where C = A005596 is Artin's constant.
Conjecture: if we further define
   Q(N,b) = # {p prime, p <= N, p == b (mod 8), p in this sequence},
then we have:
   Q(N,3) ~ (1/2)*Q(N) ~ C*Pi(N,3);
   Q(N,5) ~ (1/2)*Q(N) ~ C*Pi(N,5). (End)
Conjecture: for a prime p > 5, p has primitive root 2 iff p == +-3 (mod 8) divides 2^k + 3 for some k < p - 1 and divides 2^m + 5 for some m < p - 1. It seems that all primes of the form 2^k + 3 for k <> 2 (A057732) have primitive root 2. - Thomas Ordowski, Nov 27 2023

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 864.
E. Bach and Jeffrey Shallit, Algorithmic Number Theory, I; see p. 221.
J. H. Conway and R. K. Guy, The Book of Numbers, Copernicus Press, New York, 1996; see p. 169.
M. Kraitchik, Recherches sur la Théorie des Nombres. Gauthiers-Villars, Paris, Vol. 1, 1924, Vol. 2, 1929, see Vol. 1, p. 56.
Lehmer, D. H. and Lehmer, Emma; Heuristics, anyone? in Studies in mathematical analysis and related topics, pp. 202-210, Stanford Univ. Press, Stanford, Calif., 1962.
Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See p. 20.
D. Shanks, Solved and Unsolved Problems in Number Theory, 2nd. ed., Chelsea, 1978, p. 81.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Antti Karttunen, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
Joerg Arndt, Matters Computational (The Fxtbook), pp. 876-878.
Richard Bartels, Generalized Loewy Length of Cohen-Macaulay Local and Graded Rings, arXiv:2308.14932 [math.AC], 2023. See p. 10.
J. Conde, M. Miller, J. M. Miret, and K. Saurav, On the Nonexistence of Almost Moore Digraphs of Degree Four and Five, Mathematics in Computer Science, 9(2) (2015), 145-149.
Jonathan Detchart and Jérôme Lacan, Improving the coding speed of erasure codes with polynomial ring transforms, arXiv:1709.00178 [cs.IT], 2017.
K. Dilcher and L. Ericksen, Reducibility and irreducibility of Stern (0, 1)-polynomials, Communications in Mathematics, 22 (2014), 77-102.
Gabriele Fici and Estéban Gabory, Generalized De Bruijn Words, Invertible Necklaces, and the Burrows-Wheeler Transform, arXiv:2502.12844 [math.CO], 2025. See p. 12.
R. Gupta and M. R. Murty, A remark on Artin's conjecture, Invent. Math. 78 (1984), 127-230.
C. Hooley, On Artin's conjecture, J. Reine Angewandte Math., 225 (1967), 209-220.
Florian Ingels, Anaïs Denis, and Bastien Cazaux, Decomposing Words for Enhanced Compression: Exploring the Number of Runs in the Extended Burrows-Wheeler Transform, arXiv:2506.04926 [cs.DS], 2025. See p. 15.
Robert Jackson, Dmitriy Rumynin and Oleg V. Zaboronski, An approach to RAID-6 based on cyclic groups, Applied Mathematics & Information Sciences, 5(2) (2011), 148-170.
Jonas Kaiser, On the relationship between the Collatz conjecture and Mersenne prime numbers, arXiv:1608.00862 [math.GM], 2016.
Sihem Mesnager and Jean-Pierre Flori, A note on hyper-bent functions via Dillon-like exponents, IACR, Report 2012/033, 2012.
F. Pillichshammer, Bounds for the quality parameter of digital shift nets over Z_2, Finite Fields Applic., 8 (2002), 444-454.
Pieter Moree, Artin's primitive root conjecture-a survey, arXiv:math/0412262 [math.NT], 2004-2012.
Paul Pollack, Bounded gaps between primes with a given primitive root, arXiv:1404.4007 [math.NT], 2014.
Vladimir Shevelev, On the Newman sum over multiples of a prime with a primitive or semiprimitive root 2, arXiv:0710.1354 [math.NT], 2007.
Stephan Tornier, Groups Acting on Trees With Prescribed Local Action, arXiv:2002.09876 [math.GR], 2020.
Qifu Tyler Sun, Hanqi Tang, Zongpeng Li, Xiaolong Yang, and Keping Long, Circular-shift Linear Network Codes with Arbitrary Odd Block Lengths, arXiv:1806.04635 [cs.IT], 2018.
Eric Weisstein's World of Mathematics, Artin's constant.
Wikipedia, Artin's conjecture on primitive roots.
Index entries for sequences related to Artin's conjecture
Index entries for primes by primitive root

Cf. A001123, A001913, A001917, A005596 (Artin's constant), A050229, A071642, A127209, A163782, A292270.
Cf. A002326 for the multiplicative order of 2 mod 2n+1. (Alternatively, the least positive value of m such that 2n+1 divides 2^m-1).
Cf. A216838 (Odd primes for which 2 is not a primitive root).

Select[ Prime@Range@200, PrimitiveRoot@# == 2 &] (* Robert G. Wilson v, May 11 2001 *)
pr = 2; Select[Prime[Range[200]], MultiplicativeOrder[pr, # ] == # - 1 &] (* N. J. A. Sloane, Jun 01 2010 *)

forprime(p=3, 1000, if(znorder(Mod(2, p))==(p-1), print1(p,", "))); \\ [corrected by Michel Marcus, Oct 08 2014]

from itertools import islice
from sympy import nextprime, is_primitive_root
def A001122_gen(): # generator of terms
    p = 2
    while (p:=nextprime(p)):
        if is_primitive_root(2,p):
            yield p
A001122_list = list(islice(A001122_gen(),30)) # Chai Wah Wu, Feb 13 2023

Delta(a(n),2^a(n)*x) = a(n)*Delta(a(n),2*x), where Delta(k,x) is the difference between numbers of evil(A001969) and odious(A000069) integers divisible by k in interval [0,x). - Vladimir Shevelev, Aug 30 2013

For n >= 2, a(n) = 1 + 2*A163782(n-1). - Antti Karttunen, Oct 07 2017

A014580 Binary irreducible polynomials (primes in the ring GF(2)[X]), evaluated at X=2.

Original entry on oeis.org

2, 3, 7, 11, 13, 19, 25, 31, 37, 41, 47, 55, 59, 61, 67, 73, 87, 91, 97, 103, 109, 115, 117, 131, 137, 143, 145, 157, 167, 171, 185, 191, 193, 203, 211, 213, 229, 239, 241, 247, 253, 283, 285, 299, 301, 313, 319, 333, 351, 355, 357, 361, 369, 375

Offset: 1

David Petry (petry(AT)accessone.com)

nonn

Or, binary irreducible polynomials, interpreted as binary vectors, then written in base 10.
The numbers {a(n)} are a subset of the set {A206074}. - Thomas Ordowski, Feb 21 2014
2^n - 1 is a term if and only if n = 2 or n is a prime and 2 is a primitive root modulo n. - Jianing Song, May 10 2021
For odd k, k is a term if and only if binary_reverse(k) = A145341((k+1)/2) is. - Joerg Arndt and Jianing Song, May 10 2021

			x^4 + x^3 + 1 -> 16+8+1 = 25. Or, x^4 + x^3 + 1 -> 11001 (binary) = 25 (decimal).

A.H.M. Smeets, Table of n, a(n) for n = 1..20000 (first 1377 terms from T. D. Noe)
Index entries for sequences operating on GF(2)[X]-polynomials

Written in binary: A058943.
Number of degree-n irreducible polynomials: A001037, see also A000031.
Multiplication table: A048720.
Characteristic function: A091225. Inverse: A091227. a(n) = A091202(A000040(n)). Almost complement of A091242. Union of A091206 & A091214 and also of A091250 & A091252. First differences: A091223. Apart from a(1) and a(2), a subsequence of A092246 and hence A000069.
Table of irreducible factors of n: A256170.
Irreducible polynomials satisfying particular conditions: A071642, A132447, A132449, A132453, A162570.
Factorization sentinel: A278239.
Sequences analyzing the difference between factorization into GF(2)[X] irreducibles and ordinary prime factorization of the corresponding integer: A234741, A234742, A235032, A235033, A235034, A235035, A235040, A236850, A325386, A325559, A325560, A325563, A325641, A325642, A325643.
Factorization-preserving isomorphisms: A091203, A091204, A235041, A235042.
See A115871 for sequences related to cross-domain congruences.
Functions based on the irreducibles: A305421, A305422.

fQ[n_] := Block[{ply = Plus @@ (Reverse@ IntegerDigits[n, 2] x^Range[0, Floor@ Log2@ n])}, ply == Factor[ply, Modulus -> 2] && n != 2^Floor@ Log2@ n]; fQ[2] = True; Select[ Range@ 378, fQ] (* Robert G. Wilson v, Aug 12 2011 *)
Reap[Do[If[IrreduciblePolynomialQ[IntegerDigits[n, 2] . x^Reverse[Range[0, Floor[Log[2, n]]]], Modulus -> 2], Sow[n]], {n, 2, 1000}]][[2, 1]] (* Jean-François Alcover, Nov 21 2016 *)

is(n)=polisirreducible(Pol(binary(n))*Mod(1,2)) \\ Charles R Greathouse IV, Mar 22 2013

A163782 a(n) is the n-th J_2-prime (Josephus_2 prime).

Original entry on oeis.org

2, 5, 6, 9, 14, 18, 26, 29, 30, 33, 41, 50, 53, 65, 69, 74, 81, 86, 89, 90, 98, 105, 113, 134, 146, 158, 173, 174, 186, 189, 194, 209, 210, 221, 230, 233, 245, 254, 261, 270, 273, 278, 281, 293, 306, 309, 326, 329

Offset: 1

Peter R. J. Asveld, Aug 05 2009

nonn

Place the numbers 1..N (N>=2) on a circle and cyclically mark the 2nd unmarked number until all N numbers are marked. The order in which the N numbers are marked defines a permutation; N is a J_2-prime if this permutation consists of a single cycle of length N.
The resulting permutation can be written as p(m,N) = (2N+1-||2N+1-m||)/2 (1 <= m <= N), where ||x|| is the odd number such that x/||x|| is a power of 2. E.g., ||16||=1 and ||120||=15.
No formula is known for a(n): the J_2-primes have been found by exhaustive search (however, see the CROSS-REFERENCES). But we have: (1) N is J_2-prime iff p=2N+1 is a prime number and +2 generates Z_p^* (the multiplicative group of Z_p). (2) N is J_2-prime iff p=2N+1 is a prime number and exactly one of the following holds: (a) N == 1 (mod 4) and +2 generates Z_p^* but -2 does not, (b) N == 2 (mod 4) and both +2 and -2 generate Z_p^*.

			p(1,5)=3, p(2,5)=1, p(3,5)=5, p(4,5)=2 and p(5,5)=4.
So p=(1 3 5 4 2) and 5 is J_2-prime.

R. L. Graham, D. E. Knuth & O. Patashnik, Concrete Mathematics (1989), Addison-Wesley, Reading, MA. Sections 1.3 & 3.3.

P. R. J. Asveld, Table of n, a(n) for n = 1..6706
Jean-Paul Allouche, Manon Stipulanti, and Jia-Yan Yao, Doubling modulo odd integers, generalizations, and unexpected occurrences, arXiv:2504.17564 [math.NT], 2025.
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; alternative link.
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.
Eric Weisstein's World of Mathematics, Josephus Problem
Wikipedia, Josephus Problem
Index entries for sequences related to the Josephus Problem

A163783 through A163800 for J_3- through J_20-primes.
Considered as sets, A163782 is the union of A163777 and A163779, it equals the difference of A054639 and A163780, and 2*a(n) results in A071642.
Cf. A051732, A025480.

isJ2Prime(int n) { // for n > 1
  int count = 0, leader = 0;
  if (n % 4 == 1 || n % 4 == 2) { // small optimization
    do {
      leader = A025480(leader + n);
      count++;
    } while (leader != 0);
  }
  return count == n;
} // Joe Nellis, Jan 27 2023

lst = {};
Do[If[IntegerQ[(2^n + 1)/(2 n + 1)] && PrimitiveRoot[2 n + 1] == 2,
AppendTo[lst, n]], {n, 2, 10^5}]; lst (* Hilko Koning, Sep 21 2021 *)

Follow(s,f)={my(t=f(s),k=1); while(t>s, k++; t=f(t)); if(s==t, k, 0)}
ok(n)={my(d=2*n+1); n>1&&n==Follow(1,i->(d-((d-i)>>valuation(d-i, 2)))/2)}
select(n->ok(n),[1..1000]) \\ Andrew Howroyd, Nov 11 2017

forprime(p=5, 2000, if(znorder(Mod(2, p))==p-1, print1((p-1)/2, ", "))); \\ Andrew Howroyd, Nov 11 2017

a(n) = A071642(n+3)/2.

A054639 Queneau numbers: numbers n such that the Queneau-Daniel permutation {1, 2, 3, ..., n} -> {n, 1, n-1, 2, n-2, 3, ...} is of order n.

Original entry on oeis.org

1, 2, 3, 5, 6, 9, 11, 14, 18, 23, 26, 29, 30, 33, 35, 39, 41, 50, 51, 53, 65, 69, 74, 81, 83, 86, 89, 90, 95, 98, 99, 105, 113, 119, 131, 134, 135, 146, 155, 158, 173, 174, 179, 183, 186, 189, 191, 194, 209, 210, 221, 230, 231, 233, 239

Offset: 1

Gilles Esposito-Farese (gef(AT)cpt.univ-mrs.fr), May 17 2000

nonn

The troubadour Arnaut Daniel composed sestinas based on the permutation 123456 -> 615243, which cycles after 6 iterations.
Roubaud quotes the number 141, but the corresponding Queneau-Daniel permutation is only of order 47 = 141/3.
This appears to coincide with the numbers n such that a type-2 optimal normal basis exists for GF(2^n) over GF(2). But are these two sequences really the same? - Joerg Arndt, Feb 11 2008
The answer is Yes - see Theorem 2 of the Dumas reference. [Jean-Guillaume Dumas (Jean-Guillaume.Dumas(AT)imag.fr), Mar 20 2008]
From Peter R. J. Asveld, Aug 17 2009: (Start)
a(n) is the n-th T-prime (Twist prime). For N >= 2, the family of twist permutations is defined by
p(m,N) == +2m (mod 2N+1) if 1 <= m < k = ceiling((N+1)/2),
p(m,N) == -2m (mod 2N+1) if k <= m < N.
N is T-prime if p(m,N) consists of a single cycle of length N.
The twist permutation is the inverse of the Queneau-Daniel permutation.
N is T-prime iff p=2N+1 is a prime number and exactly one of the following three conditions holds;
(1) N == 1 (mod 4) and +2 generates Z_p^* (the multiplicative group of Z_p) but -2 does not,
(2) N == 2 (mod 4) and both +2 and -2 generate Z_p^*,
(3) N == 3 (mod 4) and -2 generate Z_p^* but +2 does not. (End)
The sequence name says the permutation is of order n, but P. R. J. Asveld's comment says it's an n-cycle. Is there a proof that those conditions are equivalent for the Queneau-Daniel permutation? (They are not equivalent for any arbitrary permutation; e.g., (123)(45)(6) has order 6 but isn't a 6-cycle.) More generally, I have found that for all n <= 9450, (order of Queneau-Daniel permutation) = (length of orbit of 1) = A003558(n). Does this hold for all n? - David Wasserman, Aug 30 2011

			For N=6 and N=7 we obtain the permutations (1 2 4 5 3 6) and (1 2 4 7)(3 6)(5): 6 is T-prime, but 7 is not. - _Peter R. J. Asveld_, Aug 17 2009

Raymond Queneau, Note complémentaire sur la Sextaine, Subsidia Pataphysica 1 (1963), pp. 79-80.
Jacques Roubaud, Bibliothèque Oulipienne No 65 (1992) and 66 (1993).

P. R. J. Asveld, Table of n, a(n) for n = 1..10085
Jean-Paul Allouche, Manon Stipulanti, and Jia-Yan Yao, Doubling modulo odd integers, generalizations, and unexpected occurrences, arXiv:2504.17564 [math.NT], 2025.
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, 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, Queneau Numbers--Recent Results and a Bibliography, University of Twente, 2013.
P. R. J. Asveld, Permuting Operations on Strings-Their Permutations and Their Primes, Twente University of Technology, 2014.
Michèle Audin, Poésie, Spirales, et Battements de Cartes, Images des Mathématiques, CNRS, 2019 (in French).
M. Bringer, Sur un problème de R. Queneau, Math. Sci. Humaines No. 25 (1969) 13-20.
Jean-Guillaume Dumas, Caractérisation des Quenines et leur représentation spirale, Mathématiques et Sciences Humaines, Centre de Mathématique Sociale et de statistique, EPHE, 2008, 184 (4), pp. 9-23, hal-00188240.
G. Esposito-Farese, C program
Index entries for sequences related to the Josephus Problem

Not to be confused with Queneau's "s-additive sequences", see A003044.
A005384 is a subsequence.
Union of A163782 (Josephus_2-primes) and A163781 (dual Josephus_2-primes); also the union of A163777 (Archimedes_0-primes) and A163778 (Archimedes_1-primes); also the union of A071642/2 (shuffle primes) and A163776/2 (dual shuffle primes). - Peter R. J. Asveld, Aug 17 2009
Cf. A216371, A003558 (for which a(n) == n).

QD:= proc(n) local i;
  if n::even then map(op,[seq([n-i,i+1],i=0..n/2-1)])
  else map(op, [seq([n-i,i+1],i=0..(n-1)/2-1),[(n+1)/2]])
  fi
end proc:
select(n -> GroupTheory:-PermOrder(Perm(QD(n)))=n, [$1..1000]); # Robert Israel, May 01 2016

a[p_] := Sum[Cos[2^n Pi/((2 p + 1) )], {n, 1, p}];
Select[Range[500],Reduce[a[#] == -1/2, Rationals] &] (* Gerry Martens, May 01 2016 *)

is(n)=
{
    if (n==1, return(1));
    my( m=n%4 );
    if ( m==4, return(0) );
    my(p=2*n+1, r=znorder(Mod(2,p)));
    if ( !isprime(p), return(0) );
    if ( m==3 && r==n, return(1) );
    if ( r==2*n, return(1) ); \\ r == 1 or 2
    return(0);
}
for(n=1,10^3, if(is(n),print1(n,", ")) );
\\ Joerg Arndt, May 02 2016

a(n) = (A216371(n)-1)/2. - L. Edson Jeffery, Dec 18 2012

a(n) >> n log n, and on the Bateman-Horn-Stemmler conjecture a(n) << n log^2 n. I imagine a(n) ≍ n log n, and numerics suggest that perhaps a(n) ~ kn log n for some constant k (which seems to be around 1.122). - Charles R Greathouse IV, Aug 02 2023

A136415 Numbers n such that a type-3 Gaussian normal basis over GF(2^n) exists.

Original entry on oeis.org

4, 6, 12, 14, 20, 22, 46, 52, 54, 60, 70, 76, 92, 94, 116, 124, 126, 140, 166, 174, 180, 182, 204, 206, 214, 220, 230, 236, 244, 252, 262, 276, 284, 286, 292, 294, 302, 332, 340, 350, 356, 364, 372, 374, 390, 404, 412, 430, 460, 484, 494, 510, 516, 526, 532

Offset: 1

Joerg Arndt, Mar 31 2008

nonn

A type-t Gaussian normal basis exists for GF(2^n) if p=n*t+1 is prime and gcd(n,(p-1)/ord(2 mod p))==1.

Type-1 basis correspond to sequence A071642, type-2 basis to A054639.

			12 is in the list because 3*12+1=37 is prime and the index of 2 mod 37 (==36/ord(2 mod 37)==1, 2 is a generator mod 37) is coprime to 12.

Joerg Arndt, Mar 31 2008, Table of n, a(n) for n = 1..201
Joerg Arndt, Matters Computational (The Fxtbook), section 42.9 "Gaussian normal bases", pp.914-920

Cf. A071642, A054639.

gauss_test(n, t)=
{ /* test whether a type-t Gaussian normal basis exists for GF(2^n) */
  local( p, r2, g, d );
  p = t*n + 1;
  if ( !isprime(p), return( 0 ) );
  if ( p<=2, return( 0 ) );
  r2 = znorder( Mod(2, p) );
  d = (p-1)/r2;
  g = gcd(d, n);
  return ( if ( 1==g, 1, 0) );
}
/* generate this sequence: */
t=3;ct=1;for(n=1,10^7,if(gauss_test(n,t), print1(n,", ");ct+=1;if(ct>200,break())))

A163776 a(n) is the n-th dS-prime (dual Shuffle prime).

Original entry on oeis.org

4, 6, 12, 22, 28, 36, 46, 52, 60, 70, 78, 100, 102, 148, 166, 172, 180, 190, 196, 198, 238, 262, 268, 270, 292, 310, 316, 348, 358, 366, 372, 382, 388, 420, 460, 462, 478, 486, 502, 508, 540, 556, 598, 606, 612, 646, 652, 660, 676, 700, 708, 718, 742, 750, 756

Offset: 1

Peter R. J. Asveld, Aug 13 2009

nonn

For N>=2, the family of dual 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

No formula is known for a(n): the dS-primes have been found by exhaustive search. But we have: N is dS-prime iff p=N+1 is an odd prime number and -2 generates Z_p^* (the multiplicative group of Z_p).

			For N=6 and N=10 we obtain the permutations (1 5 4 6 2 3) and (1 9 4 3 5)(2 7 8 6 10): 6 is dS-prime, but 10 is not.

P. R. J. Asveld, Table of n, a(n) for n=1..3612
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. University link.
Index entries for sequences related to the Josephus Problem

a(n)/2 results in the dual Josephus_2-primes (A163781). Considered as sets a(n)/2 is the union of A163777 and A163780. If b(n) denotes the shuffle primes (A071642), 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).

a(n) = 2*A163781(n).

a(33)-a(55) from Andrew Howroyd, Nov 11 2017

A050229 Numbers k such that for any x in 1..k-1 there exists a y in 0..k-2 such that x^2 == 2^y (mod k).

Original entry on oeis.org

1, 2, 3, 5, 11, 13, 19, 29, 37, 53, 59, 61, 67, 83, 101, 107, 131, 139, 149, 163, 173, 179, 181, 197, 211, 227, 269, 293, 317, 347, 349, 373, 379, 389, 419, 421, 443, 461, 467, 491, 509, 523, 541, 547, 557, 563, 587, 613, 619, 653, 659, 661, 677, 701, 709, 757, 773, 787, 797, 821, 827, 829, 853, 859, 877, 883, 907, 941, 947

Offset: 1

Benoit Cloitre, May 08 2003

nonn

It seems that the sequence consists of {1,2} union A001122. The sequence differs from A082595 because here the multiplicity is not important (see example: P contains two 5's and Q is required to have at least one 5, not necessarily 2 5's).
Numbers k for which there is a permutation of 0..k-1 such that each number is the sum of all the previous numbers, plus 1, mod k. - R. H. Hardin, Dec 28 2007
Positive numbers k such that x^(k-1) + x^(k-2) + x^(k-3) + ... + x + 1 is irreducible over GF(2). - Arkadiusz Wesolowski, Nov 20 2012
All terms > 1 are prime. Appears to be set of numbers k such that the sequence 2^n mod k has period length of k-1. - Gary Detlefs, May 15 2014

			The set of values for x^2 mod 19, 1<=x<=18, is P=[1, 4, 9, 16, 6, 17, 11, 7, 5, 5, 7, 11, 17, 6, 16, 9, 4, 1], the set of values for 2^y mod 19, 0<=y<=n-2 is Q= [1, 2, 4, 8, 16, 13, 7, 14, 9, 18, 17, 15, 11, 3, 6, 12, 5, 10] which contains all values in P, hence 19 is in the sequence.

Cf. A001122, A082595.

for(n=1,450,if(sum(y=1,n-1,if(setsearch(Set(vector(n-1,x,2^(x-1)%n)),y),0,1))==0,print1(n,",")))

a(n) = A071642(n) + 1. - Arkadiusz Wesolowski, Nov 20 2012

More terms from R. H. Hardin, Dec 28 2007

A087481 Number of polynomials of the form x^n +- x^(n-1) +- x^(n-2) +- ... +- 1 irreducible over the integers.

Original entry on oeis.org

2, 4, 4, 16, 12, 48, 64, 192, 260, 1024, 1128, 4096, 4480, 13310, 20620, 65434, 76376, 262144, 358532, 932134, 1391720, 4194090, 5447256, 16570740, 23153832, 61696126, 97361128

Offset: 1

T. D. Noe, Sep 09 2003

For each n, there are 2^n polynomials to consider. All 2^n polynomials are irreducible for n = 1, 2, 4, 10, 12, 18, which is sequence A071642. For those values of n, n+1 is a prime in Artin's primitive root conjecture (A001122).

Since p(x) is irreducible iff (-1)^n*p(-x) is irreducible, all terms are even. - Robert Israel, Dec 22 2014

Eric Weisstein's World of Mathematics, Irreducible Polynomial
Math Overflow, Irreducible polynomials with constrained coefficients

Cf. A001122, A071642, A087482 (irreducible binary polynomials).

f:= proc(n) local t, j, p0, p;
   p0:= add(x^j, j = 0 .. n);
   2*nops(select(s -> irreduc(p0 - 2*add(x^(j-1), j = s)), combinat:-powerset(n-1)));
end proc:
seq(f(n),n=1..18); # Robert Israel, Dec 22 2014

Irreducible[p_, n_] := Module[{f}, f=FactorList[p, Modulus->n]; Length[f]==1 || Simplify[p-f[[2, 1]]]===0]; Table[xx=x^Range[0, n-1]; cnt=0; Do[p=x^n+xx.(2*IntegerDigits[i, 2, n]-1); If[Irreducible[p, 0], cnt++ ], {i, 0, 2^n-1}]; cnt, {n, 18}]

R.=Z[]; a(n) = sum((x^n + sum(( 2 * ((b & (1<> d) - 1 ) * x^d for d in range(n))).is_irreducible() for b in range(2^n))

a(n) = 2^n for n a term of A071642; see first comment.

a(19) from Robert Israel, Dec 22 2014

a(20)-a(27) from Lucas A. Brown, May 19 2023

A321580 Numbers k such that it is possible to reverse a deck of k cards by a sequence of perfect Faro shuffles with cut.

Original entry on oeis.org

1, 2, 4, 8, 10, 12, 16, 18, 24, 26, 28, 32, 36, 40, 42, 52, 56, 58, 60, 64, 66, 80, 82, 96, 98, 100, 106, 108, 112, 120, 124, 128, 130, 136, 138, 144, 148, 156, 162, 168, 170, 172, 176, 178, 180, 184, 192, 196, 200, 204, 208, 210, 226, 228, 240, 242, 248, 250

Offset: 1

Pedro Menezes, Nov 13 2018

nonn

Except for 1, it isn't possible to shuffle backwards an odd number of cards.

			For a deck of 4 cards we'll have the following sequence of shuffles: 1234, 2413, 4321, 3142, 1234. Observe that the reverse order (4321) of 1234 appears in the sequence of shuffles.
For a deck of 5 cards: 12345, 24135, 43215, 31425, 12345. Observe that the reverse order (54321) of 12345 does not appear in the sequence of shuffles.

Andrew Howroyd, Table of n, a(n) for n = 1..2000
Wikipedia, Faro shuffle

Cf. A024222, A071642, A321512.

shuffle(v)={my(h=#v\2); vector(#v, i, if(i<=h, 2*i, 2*(i-h)-1))}
permcycs(v)={my(f=vector(#v), L=List()); for(i=1, #v, if(!f[i], my(T=List(), j=i); while(!f[j], f[j]=1; listput(T,j); j=v[j]); listput(L, Vec(T)))); Vec(L)}
ok(n)={my(v=permcycs(shuffle([1..n])), e=-1); for(k=1, #v, my(p=v[k]); if(#p>1||n%2==0||2*p[1]<>n+1, my(h=#p\2); if(e<0, e=valuation(#p,2)); if(valuation(#p,2)<>e || e==0 || p[1..h]+p[h+1..2*h]<>vector(h,i,n+1), return(0)))); 1} \\ Andrew Howroyd, Nov 13 2018

for n in range(1, 501):
    cards = [i for i in range(1, n + 1)]
    reverse = cards[::-1]
    shuffled = cards.copy()
    reversein = False
    for i in range(n):
        evens = shuffled[1::2]
        odds = shuffled[0::2]
        shuffled = evens + odds
        if shuffled == reverse:
            reversein = True
            print(n, end=", ")
            break

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

Original entry on oeis.org

1, 2, 6, 16, 22, 36, 42, 46, 52, 72, 82, 96, 102, 106, 112, 136, 156, 166, 172, 192, 196, 222, 226, 232, 256, 262, 276, 282, 292, 306, 316, 346, 352, 372, 382, 396, 432, 442, 462, 466, 502, 522, 546, 556, 562, 576, 586, 592, 606, 612, 616, 646, 652, 672, 676

Offset: 1

Robert G. Wilson v, Jun 22 2002

Numbers k = p - 1 such that p is a prime with primitive root 5. - Joerg Arndt, Jun 25 2020

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A071642. Contained in A006093.

filter:= proc(n)
isprime(n+1) and numtheory:-order(5,n+1)=n
end proc:
select(filter, [$1..1000]); # Robert Israel, Jun 25 2020

Select[Prime[Range[1000]], MultiplicativeOrder[5, #] == # - 1&] - 1 (* Jean-François Alcover, Aug 16 2020 *)

forprime(p=2, 10^3, if(p==5,next()); if(znorder(Mod(5,p))==p-1, print1(p-1,", "))); \\ Joerg Arndt, Jun 25 2020

a(n) = A019335(n) - 1. - Joerg Arndt, Jun 25 2020

a(1)=1 inserted by Robert Israel, Jun 24 2020

Showing 1-10 of 17 results. Next

cp's OEIS Frontend

A001122 Primes with primitive root 2.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A014580 Binary irreducible polynomials (primes in the ring GF(2)[X]), evaluated at X=2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A163782 a(n) is the n-th J_2-prime (Josephus_2 prime).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Java

Mathematica

PARI

PARI

Formula

A054639 Queneau numbers: numbers n such that the Queneau-Daniel permutation {1, 2, 3, ..., n} -> {n, 1, n-1, 2, n-2, 3, ...} is of order n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A136415 Numbers n such that a type-3 Gaussian normal basis over GF(2^n) exists.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A163776 a(n) is the n-th dS-prime (dual Shuffle prime).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A050229 Numbers k such that for any x in 1..k-1 there exists a y in 0..k-2 such that x^2 == 2^y (mod k).

Views

Author

Keywords

Comments

Examples