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.
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
KEYWORD
nonn
AUTHOR
Peter R. J. Asveld, Aug 17 2009
EXTENSIONS
a(37)-a(55) from Andrew Howroyd, Nov 11 2017
STATUS
approved