cp's OEIS Frontend

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

%I A163782 #62 Apr 25 2025 03:07:15
%S A163782 2,5,6,9,14,18,26,29,30,33,41,50,53,65,69,74,81,86,89,90,98,105,113,
%T A163782 134,146,158,173,174,186,189,194,209,210,221,230,233,245,254,261,270,
%U A163782 273,278,281,293,306,309,326,329
%N A163782 a(n) is the n-th J_2-prime (Josephus_2 prime).
%C A163782 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 A163782 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 A163782 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 A163782 R. L. Graham, D. E. Knuth & O. Patashnik, Concrete Mathematics (1989), Addison-Wesley, Reading, MA. Sections 1.3 & 3.3.
%H A163782 P. R. J. Asveld, <a href="/A163782/b163782.txt">Table of n, a(n) for n = 1..6706</a>
%H A163782 Jean-Paul Allouche, Manon Stipulanti, and Jia-Yan Yao, <a href="https://arxiv.org/abs/2504.17564">Doubling modulo odd integers, generalizations, and unexpected occurrences</a>, arXiv:2504.17564 [math.NT], 2025.
%H A163782 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 A163782 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 A163782 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 A163782 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/JosephusProblem.html">Josephus Problem</a>
%H A163782 Wikipedia, <a href="https://en.wikipedia.org/wiki/Josephus_problem">Josephus Problem</a>
%H A163782 <a href="/index/J#Josephus">Index entries for sequences related to the Josephus Problem</a>
%F A163782 a(n) = A071642(n+3)/2.
%e A163782 p(1,5)=3, p(2,5)=1, p(3,5)=5, p(4,5)=2 and p(5,5)=4.
%e A163782 So p=(1 3 5 4 2) and 5 is J_2-prime.
%t A163782 lst = {};
%t A163782 Do[If[IntegerQ[(2^n + 1)/(2 n + 1)] && PrimitiveRoot[2 n + 1] == 2,
%t A163782 AppendTo[lst, n]], {n, 2, 10^5}]; lst (* _Hilko Koning_, Sep 21 2021 *)
%o A163782 (PARI)
%o A163782 Follow(s,f)={my(t=f(s),k=1); while(t>s, k++; t=f(t)); if(s==t, k, 0)}
%o A163782 ok(n)={my(d=2*n+1); n>1&&n==Follow(1,i->(d-((d-i)>>valuation(d-i, 2)))/2)}
%o A163782 select(n->ok(n),[1..1000]) \\ _Andrew Howroyd_, Nov 11 2017
%o A163782 (PARI)
%o A163782 forprime(p=5, 2000, if(znorder(Mod(2, p))==p-1, print1((p-1)/2, ", "))); \\ _Andrew Howroyd_, Nov 11 2017
%o A163782 (Java)
%o A163782 isJ2Prime(int n) { // for n > 1
%o A163782   int count = 0, leader = 0;
%o A163782   if (n % 4 == 1 || n % 4 == 2) { // small optimization
%o A163782     do {
%o A163782       leader = A025480(leader + n);
%o A163782       count++;
%o A163782     } while (leader != 0);
%o A163782   }
%o A163782   return count == n;
%o A163782 } // _Joe Nellis_, Jan 27 2023
%Y A163782 A163783 through A163800 for J_3- through J_20-primes.
%Y A163782 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 A163782 Cf. A051732, A025480.
%K A163782 nonn
%O A163782 1,1
%A A163782 _Peter R. J. Asveld_, Aug 05 2009