1

What is the direct formula for the following variation of Josephus problem?

There are $n$ persons, numbered $1$ to $n$, around a circle.. Starting from $k$-th person, every second person is eliminated. Given the $n$ and $k$, determine the index of the $x$-th person who is eliminated.

ADDED:In the first step the $k+1$th is eliminated.For n = 16,k = 6, elimination={7,9,...}

Thanks

darij grinberg
  • 17,777
  • Is number $k$ the first to be eliminated, or is it $k+2$? In any case, this just rotates the circle by $k-1$ or $k+1$ postions – Ross Millikan Feb 19 '11 at 20:25
  • @Ross Millikan:Could you please explain,I did not understand your second point. –  Feb 19 '11 at 20:31
  • Just that you can eliminate the dependence on k by renumbering the people, then add back in the k after you have solved the problem. So if there are 10 people and you start counting with 1, the sixth one eliminated is number 3 and the seventh is 7. So if you first eliminate 7 (instead of 2) the sixth one eliminated will be $3+5 \pmod {10}=8$ and the seventh will be $7+5 \pmod {10}=2$ – Ross Millikan Feb 19 '11 at 20:34

2 Answers2

1

If you go to the Wikipedia page, there is a reference at the bottom

Ross Millikan
  • 374,822
-1

I made a video very closely related to this question. There's a link to the video at: http://oeis.org/A006165

Dale Gerdemann
  • 1