Day 23: CM, Page 10

Day 23: The Josephus problem continued. Yesterday we found a recursive solution for the Josephus problem with an even number of people. With an odd number of people, the recursive solution is similar.

Consider J(2n + 1). If you start with 1 2 3 4 5 6 7 8 9, after the first round of elimination you have 1 3 5 7 9. But wait! This isn't right. To continue the elimination process, we would need to eliminate 1 next, so new sequence isn't quite correct - it's off by one if we want to skip the first member of the sequence on the second iteration. To keep the iteration consistent (always skipping the first element in a sequence), we need to eliminate one more element. So 1 2 3 4 5 6 7 8 9 is actually the same as 3 5 7 9 where 1 is included in the first round of elimination. Now on the second round of iteration we start with 5 as expected. 3 5 7 9 is the same problem as 1 2 3 4 except that each number is doubled and incremented by 1. So J(2n + 1) = 2(J(n)) + 1.

So we have:
J(1) = 1
J(2n) = 2(J(n)) - 1
J(2n + 1) = 2(J(n)) + 1

And with that we have a recursive formula to describe a solution to the problem. The authors use the recursive formula to describe the pattern we saw a couple of days ago, but they find a better notation to represent the closed form.

J(n) = J(2^m + l) = 2l + 1

Where 2^m <= n < 2^(m+1) and l is the remainder (or leftover) of n/2^m. Also note: l < 2^m

With this we have a closed form representation of the Josephus problem. Tomorrow we'll need to prove it, and authors have some additional interesting observations about the problem.