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

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,1

Comments

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)<y and x=F(x,y)*(-2)^t (mod y) for the smallest t>=0. Note that F(2k + 1,y)=2k + 1 for 2k + 1<y, as t=0 applies. N is a dJ_2 prime if this permutation consists of a single cycle of length N.

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.

References

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

Links

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

Example

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.

Mathematica

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

Prog

(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

Crossrefs

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).

Sequence in context: A042944 A374913 A361124 * A090304 A005211 A298702

Adjacent sequences: A163778 A163779 A163780 * A163782 A163783 A163784

Keyword

nonn

Author

Peter R. J. Asveld, Aug 17 2009

Extensions

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

Status

approved