Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

We are given $1,\ldots,n$ numbers. Let's say we are to save a given number element $k$ for last in elimination. We start eliminating them in the following manner. I eliminate $1$ at first. Then eliminate the next $k$th element (index $k+1$). And then keep doing the same wrapping around $n$ if needed. The numbers eliminated before don't count for elimination for counting till $k$, next time onwards. I want to find such $k$ that element given element no (say $i$) goes last in the elimination.

As sample: lets take 1 2 3 4 5 as input

Now say I want to save 5 for last. Thus min number $k=3$ in this case (ans).

Lets simulate it.
1 is eliminated first
4 goes next
3 goes next
2 goes next
and 5 is saved for last.

I need to find this minimum $(k=3)$ given $n$ and number i to save for last.

share|cite|improve this question
This is the Josephus problem. – joriki Feb 13 '13 at 11:21

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.