The recurrence hidden behind J

Why the case k = 2 is special

From now on elimination proceeds two by two, and J(n) denotes the position of the last survivor in a group of n people.

The first pass around the circle eliminates every person in an even position: 2, then 4, then 6… That is the key to everything. Two immediate consequences:

• the survivor is necessarily in an odd position;
• after this first pass exactly the odd positions remain, and the problem reduces to an identical one with half as many people.

The recurrence

Distinguish according to the parity of the starting number.

Case of 2n people. The first pass eliminates the n people in even positions and ends just before person 1. The n people in positions 1, 3, 5, …, 2n−1 remain, and counting restarts from the first one: this is the problem with n people, where the j-th renumbered person occupies position 2j − 1.

   J(2n) = 2·J(n) − 1

Case of 2n + 1 people. The first pass eliminates the even positions, then, coming back to the start, also eliminates person 1 — because the starting number is odd, counting "wraps" onto them. n people remain, in positions 3, 5, …, 2n + 1, and the j-th renumbered person occupies position 2j + 1.

   J(2n + 1) = 2·J(n) + 1

With J(1) = 1, these two relations determine J entirely.

What they say in binary

Doubling n appends a 0 on the right of its binary expansion; doubling and adding 1 appends a 1. The relations above therefore do the same thing to J as to n, except that a 0 becomes −1 and a 1 becomes +1. That parallel is what the final formula expresses: J(n) is obtained by moving the leading 1 of n to the end of its binary expansion.

   41 = 101001₂   →   J(41) = 010011₂ = 10011₂ = 19