1,1

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.

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.

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

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

Peter R. J. Asveld, Table of n, a(n) for n = 1..6706

Jean-Paul Allouche, Manon Stipulanti, and Jia-Yan Yao, Doubling modulo odd integers, generalizations, and unexpected occurrences, Math. Intelligencer, 2026. See p. 6. See also arXiv:2504.17564 [math.NT], 2025. See p. 8.

Peter R. J. Asveld, Permuting operations on strings and their relation to prime numbers, Discrete Applied Mathematics 159 (2011) 1915-1932.

Peter 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; alternative link.

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

Eric Weisstein's World of Mathematics, Josephus Problem

Wikipedia, Josephus Problem

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

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

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

lst = {};

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

AppendTo[lst, n]], {n, 2, 10^5}]; lst (* Hilko Koning, Sep 21 2021 *)

(PARI)

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

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

select(n->ok(n), [1..1000]) \\ Andrew Howroyd, Nov 11 2017

(PARI)

forprime(p=5, 2000, if(znorder(Mod(2, p))==p-1, print1((p-1)/2, ", "))); \\ Andrew Howroyd, Nov 11 2017

(Java)

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

int count = 0, leader = 0;

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

do {

leader = A025480(leader + n);

count++;

} while (leader != 0);

}

return count == n;

} // Joe Nellis, Jan 27 2023

A163783 through A163800 for J_3- through J_20-primes.

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.

Cf. A051732, A025480.

Sequence in context: A271371 A193978 A224486 * A362140 A226793 A255747

Adjacent sequences: A163779 A163780 A163781 * A163783 A163784 A163785

Peter R. J. Asveld, Aug 05 2009

approved