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

%I #34 Aug 05 2024 14:08:34

%S 2,3,6,11,14,18,23,26,30,35,39,50,51,74,83,86,90,95,98,99,119,131,134,

%T 135,146,155,158,174,179,183,186,191,194,210,230,231,239,243,251,254,

%U 270,278,299,303,306,323,326,330,338,350,354,359,371,375,378

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

%C 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.

%C 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].

%C 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:

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

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

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

%H P. R. J. Asveld, <a href="/A163781/b163781.txt">Table of n, a(n) for n=1..6756</a>

%H 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 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 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 P. R. J. Asveld, <a href="https://citeseerx.ist.psu.edu/pdf/9d8542763057ef03a22b57f87085d69497ddaf46">Permuting Operations on Strings-Their Permutations and Their Primes</a>, Twente University of Technology, 2014. <a href="http://doc.utwente.nl/67513">University link</a>.

%H <a href="/index/J#Josephus">Index entries for sequences related to the Josephus Problem</a>

%e For N=6 we have

%e m | 1 2 3 4 5 6

%e --------+----------------------

%e F(m,13) | 1 7 3 11 5 9

%e t | 0 2 0 1 0 3

%e p(m,6) | 6 3 5 1 4 2

%e So the permutation is (1 6 2 3 5 4) and 6 is dJ_2 prime.

%t okQ[n_] := Mod[n, 4] >= 2 && PrimeQ[2n+1] && MultiplicativeOrder[2, 2n+1] == If[OddQ[n], n, 2n];

%t Select[Range[1000], okQ] (* _Jean-François Alcover_, Sep 23 2019, from PARI *)

%o (PARI)

%o ok(n)={n%4>=2 && isprime(2*n+1) && znorder(Mod(2, 2*n+1)) == if(n%2,n,2*n)};

%o select(ok, [1..1000]) \\ _Andrew Howroyd_, Nov 11 2017

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

%K nonn

%O 1,1

%A _Peter R. J. Asveld_, Aug 17 2009

%E a(37)-a(55) from _Andrew Howroyd_, Nov 11 2017