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

2, 5, 6, 9, 14, 18, 26, 29, 30, 33, 41, 50, 53, 65, 69, 74, 81, 86, 89, 90, 98, 105, 113, 134, 146, 158, 173, 174, 186, 189, 194, 209, 210, 221, 230, 233, 245, 254, 261, 270, 273, 278, 281, 293, 306, 309, 326, 329

Offset

1,1

Comments

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

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

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

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.

Eric Weisstein's World of Mathematics, Josephus Problem

Wikipedia, Josephus Problem

Index entries for sequences related to the Josephus Problem

Formula

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

Example

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.

Mathematica

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 *)

Prog

(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

Crossrefs

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

Keyword

nonn

Author

Peter R. J. Asveld, Aug 05 2009

Status

approved