%I #57 Aug 05 2024 14:06:51

%S 2,5,6,9,14,18,26,29,30,33,41,50,53,65,69,74,81,86,89,90,98,105,113,

%T 134,146,158,173,174,186,189,194,209,210,221,230,233,245,254,261,270,

%U 273,278,281,293,306,309,326,329

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

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

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

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

%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="/A163782/b163782.txt">Table of n, a(n) for n = 1..6706</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; <a href="https://citeseerx.ist.psu.edu/pdf/9d8542763057ef03a22b57f87085d69497ddaf46">alternative link</a>.

%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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/JosephusProblem.html">Josephus Problem</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Josephus_problem">Josephus Problem</a>

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

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

%e p(1,5)=3, p(2,5)=1, p(3,5)=5, p(4,5)=2 and p(5,5)=4.

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

%t lst = {};

%t Do[If[IntegerQ[(2^n + 1)/(2 n + 1)] && PrimitiveRoot[2 n + 1] == 2,

%t AppendTo[lst, n]], {n, 2, 10^5}]; lst (* _Hilko Koning_, Sep 21 2021 *)

%o (PARI)

%o Follow(s,f)={my(t=f(s),k=1); while(t>s, k++; t=f(t)); if(s==t, k, 0)}

%o ok(n)={my(d=2*n+1); n>1&&n==Follow(1,i->(d-((d-i)>>valuation(d-i, 2)))/2)}

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

%o (PARI)

%o forprime(p=5, 2000, if(znorder(Mod(2, p))==p-1, print1((p-1)/2, ", "))); \\ _Andrew Howroyd_, Nov 11 2017

%o (Java)

%o isJ2Prime(int n) { // for n > 1

%o int count = 0, leader = 0;

%o if (n % 4 == 1 || n % 4 == 2) { // small optimization

%o do {

%o leader = A025480(leader + n);

%o count++;

%o } while (leader != 0);

%o }

%o return count == n;

%o } // _Joe Nellis_, Jan 27 2023

%Y A163783 through A163800 for J_3- through J_20-primes.

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

%Y Cf. A051732, A025480.

%K nonn

%O 1,1

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