A163780 -id:A163780 - cp's OEIS frontend

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

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.

A163777 Even terms in the sequence of Queneau numbers A054639.

Original entry on oeis.org

2, 6, 14, 18, 26, 30, 50, 74, 86, 90, 98, 134, 146, 158, 174, 186, 194, 210, 230, 254, 270, 278, 306, 326, 330, 338, 350, 354, 378, 386, 398, 410, 414, 426, 438, 470, 530, 554, 558, 606, 614, 618, 638, 650, 686, 690, 726, 746, 774, 810, 818, 834, 846, 866, 870

Offset: 1

Peter R. J. Asveld, Aug 11 2009

nonn

Previous name was: a(n) is the n-th A_0-prime (Archimedes_0 prime).

We have: (1) N is A_0-prime if and only if N is even, p = 2N + 1 is a prime number and both +2 and -2 generate Z_p^* (the multiplicative group of Z_p); (2) N is A_0-prime if and only if N = 2 (mod 4), p = 2N + 1 is a prime number and both +2 and -2 generate Z_p^*.

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

The A_0-primes are the even T- or Twist-primes, these T-primes are equal to the Queneau-numbers (A054639). For the related A_1-, A^+_1- and A^-_1-primes, see A163778, A163779 and A163780. Considered as sets A163777 is the intersection of the Josephus_2-primes (A163782) and the dual Josephus_2-primes (A163781), it also equals the difference of A054639 and the A_1-primes (A163779).

Cf. A137310.

okQ[n_] := EvenQ[n] && PrimeQ[2n+1] && MultiplicativeOrder[2, 2n+1] == 2n;
Select[Range[1000], okQ] (* Jean-François Alcover, Sep 10 2019, from PARI *)

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

ok(n)={n%2==0 && isprime(2*n+1) && znorder(Mod(2, 2*n+1)) == 2*n}
select(ok, [1..1000]) \\ Andrew Howroyd, Nov 11 2017

a(n) = 2*A137310(n). - Andrew Howroyd, Nov 11 2017

Definition simplified by Michel Marcus, May 27 2013
a(33)-a(55) from Andrew Howroyd, Nov 11 2017
New name from Joerg Arndt, Mar 23 2018, edited by M. F. Hasler, Mar 24 2018

A163778 Odd terms in A054639.

Original entry on oeis.org

3, 5, 9, 11, 23, 29, 33, 35, 39, 41, 51, 53, 65, 69, 81, 83, 89, 95, 99, 105, 113, 119, 131, 135, 155, 173, 179, 183, 189, 191, 209, 221, 231, 233, 239, 243, 245, 251, 261, 273, 281, 293, 299, 303, 309, 323, 329, 359, 371, 375, 393, 411, 413, 419, 429

Offset: 1

Peter R. J. Asveld, Aug 11 2009

nonn

Previous name was: The A_1-primes (Archimedes_1 primes).
We have: (1) N is an A_1-prime iff N is odd, p=2N+1 is a prime number and only one of +2 and -2 generates Z_p^* (the multiplicative group of Z_p); (2) N is an A_1-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 == 3 (mod 4) and -2 generates Z_p^* but +2 does not.
The A_1-primes are the odd T- or Twist-primes (the T-primes are the same as the Queneau-numbers, A054639). For the related A_0-, A^+_1- and A^-_1-primes, see A163777, A163779 and A163780. Considered as a set, the present sequence is the union of the A^+_1-primes (A163779) and the A^-_1-primes (A163780). It is also equal to the difference of A054639 and the A_0-primes (A163777).

P. R. J. Asveld, Table of n, a(n) for n=1..6706.
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.

Cf. A054639, A163777, A163779, A163780, A294434, A294673.

follow[s_, f_] := Module[{t, k}, t = f[s]; k = 1; While[t>s, k++; t = f[t]]; If[s == t, k, 0]];
okQ[n_] := n>1 && n == follow[1, Function[j, Ceiling[n/2] + (-1)^j*Ceiling[ (j-1)/2]]];
A163778 = Select[Range[1000], okQ] (* Jean-François Alcover, Jun 07 2018, after Andrew Howroyd *)

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

ok(n)={n>1 && n%2==1 && isprime(2*n+1) && znorder(Mod(2, 2*n+1)) == if(n%4==3, n, 2*n)}
select(ok, [1..1000]) \\ Andrew Howroyd, Nov 11 2017

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

New name from Joerg Arndt, Mar 23 2018

A163779 Numbers k of the form 4j + 1 such that 2k + 1 is a prime with primitive root 2.

Original entry on oeis.org

1, 5, 9, 29, 33, 41, 53, 65, 69, 81, 89, 105, 113, 173, 189, 209, 221, 233, 245, 261, 273, 281, 293, 309, 329, 393, 413, 429, 441, 453, 473, 509, 545, 561, 585, 593, 629, 641, 645, 653, 713, 725, 741, 749, 761, 765, 785, 809, 833, 873, 893, 933, 953, 965, 989, 993

Offset: 1

Peter R. J. Asveld, Aug 12 2009

nonn

Previous name was: a(n) is the n-th A^+_1-prime (Archimedes^+_1 prime).

N is A^+_1-prime iff N=1 (mod 4), p=2N+1 is a prime number and +2 generates Z_p^* (the multiplicative group of Z_p) but -2 does not.

Joerg Arndt, Table of n, a(n) for n = 1..10000 (first 3328 from P. R. J. Asveld)
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.
P. Michael Hutchins, Reworded Definition

The A^+_1-primes are the T- or Twist-primes congruent 1 (mod 4), these T-primes are equal to the Queneau-numbers (A054639). For the related A_0-, A_1- and A^-_1-primes, see A163777, A163778 and A163780. Considered as sets the union of A163779 and A163780 equals A163778, the union of A163779 and A163777 is equal to A163782 (J_2-primes).

okQ[n_] := Mod[n, 4] == 1 && PrimeQ[2n+1] && MultiplicativeOrder[2, 2n+1] == 2n;
Select[Range[1000], okQ] (* Jean-François Alcover, Jun 30 2018, after Andrew Howroyd *)

ok(n) = n%4==1 && isprime(2*n+1) && znorder(Mod(2, 2*n+1))==2*n;
select(ok, [1..1000]) \\ Andrew Howroyd, Nov 11 2017

2 * a(n) + 1 = A213051(n+1). - Joerg Arndt, Mar 23 2018

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

Term 1 prepended and new name from Joerg Arndt, Mar 23 2018

A163781 a(n) is the n-th dJ_2 prime (dual Josephus_2 prime).

Original entry on oeis.org

2, 3, 6, 11, 14, 18, 23, 26, 30, 35, 39, 50, 51, 74, 83, 86, 90, 95, 98, 99, 119, 131, 134, 135, 146, 155, 158, 174, 179, 183, 186, 191, 194, 210, 230, 231, 239, 243, 251, 254, 270, 278, 299, 303, 306, 323, 326, 330, 338, 350, 354, 359, 371, 375, 378

Offset: 1

Peter R. J. Asveld, Aug 17 2009

nonn

The family of dual Josephus_2 (or dJ_2) permutations is defined by p(m,N)=(2N + 1 - F(m,2N + 1))/2 if 1<=m<=N, N>=2, where F(x,y) is the odd number such that 1<=F(x,y)=0. Note that F(2k + 1,y)=2k + 1 for 2k + 1

dJ_2 permutations can also be defined using a numbering/elimination procedure similar to the definition of the Josephus_2 permutations in [R.L. Graham et al.], or in A163782; see [P. R. J. Asveld].

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

(a) N=2 (mod 4) and both +2 and -2 generate Z_p^*,

(b) N=3 (mod 4) and -2 generates Z_p^* but +2 does not.

			For N=6 we have
  m       | 1   2   3   4   5   6
  --------+----------------------
  F(m,13) | 1   7   3  11   5   9
  t       | 0   2   0   1   0   3
  p(m,6)  | 6   3   5   1   4   2
So the permutation is (1 6 2 3 5 4) and 6 is dJ_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..6756
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

Considered as sets the union of A163781 and A163782 (J_2 primes) equals A054639 (T-primes or Queneau numbers), their intersection is equal to A163777 (Archimedes_0 primes). A163781 equals the union of A163777 and A163780 (Archimedes^-_1 primes).

okQ[n_] := Mod[n, 4] >= 2 && PrimeQ[2n+1] && MultiplicativeOrder[2, 2n+1] == If[OddQ[n], n, 2n];
Select[Range[1000], okQ] (* Jean-François Alcover, Sep 23 2019, from PARI *)

ok(n)={n%4>=2 && isprime(2*n+1) && znorder(Mod(2, 2*n+1)) == if(n%2,n,2*n)};
select(ok, [1..1000]) \\ Andrew Howroyd, Nov 11 2017

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

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

Showing 1-6 of 6 results.

cp's OEIS Frontend

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

A163777 Even terms in the sequence of Queneau numbers A054639.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A163778 Odd terms in A054639.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Extensions

A163779 Numbers k of the form 4*j + 1 such that 2*k + 1 is a prime with primitive root 2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A163781 a(n) is the n-th dJ_2 prime (dual Josephus_2 prime).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A163779 Numbers k of the form 4j + 1 such that 2k + 1 is a prime with primitive root 2.