# The Josephus Problem: Marginal Clarifications

The book's marginal markings for the closed-form proof required additional effort on my side to understand. This post explicates the ideas of that marginal note.

The key fact is that

`J(2`

for all^{m}) = 1`m`

, and this follows immediately from our first equation,`J(2n) = 2J(n) - 1`

.

By follows immediately

the author of the note
supposedly meant the following considerations.

- Fact 1
`2`

is an even number (it can be divided by^{m}`2`

for any integer`m`

).- Fact 2
- The meaning behind
`J(2n) = 2J(n) - 1`

is that as long as we have an even number of people, the survivor is the same as in a twice smaller group minus one. - Fact 3
`2`

can be halved^{m}`m`

times before reaching a value of`1`

.

Combining these facts, we can write that

So indeed, we have confirmed — based on the given facts — that
the first person will survive whenever n is a power of
2.

Now we move to the second part of the note.

And in the general case, when

`n = 2`

, the number of people is reduced to a power of^{m}+ l`2`

after there have been`l`

executions. The first remaining person at this point, the survivor, is number`2l + 1`

.

To help us visualize what this text means, first we look at the small cases.

**Three People**

**Five People**

**Six People**

`n` |
`2` `+ l` |
`2l + 1` |
`Survivor #` |
---|---|---|---|

3 | 2^{1} + 1 |
2 × 1 + 1 | 3 |

5 | 2^{2} + 1 |
2 × 1 + 1 | 3 |

6 | 2^{2} + 2 |
2 × 2 + 1 | 5 |

Reviewing the small cases, we see that after `l`

executions we are left with
`2`

people. Hence — according to the
considerations from the first part of this post — the survivor is the first
person in this group.
^{m}

The survivor's number can be calculated by the formula `2l + 1`

, because each of
`l`

executions affects `2`

people (an executioner and an executed) and the next
(plus one) person is the first one in a left group of people (hence the
survivor, as was discussed above).

Phew! Such a small note and so much effort for its clarification.

In the next post we move on to the second part of the book and apply *repertoire
method* for evaluation of a sum in a closed form.