Forty-one rebels in a circle

The story

Flavius Josephus, a Jewish historian of the 1st century, tells himself how his life was spared. Trapped in a cave by the Romans along with forty other rebels, the group refused to surrender and decided on collective suicide, following a precise protocol:

• the forty-one people stand in a circle and number themselves from 1 to 41;
• the circle is walked three by three — the first person designated is therefore number 3;
• the person designated is put to death, then removed from the circle;
• counting resumes from the next person, among the survivors;
• the last person left takes their own life.

Josephus and a friend disagreed. The question becomes: where should they stand to be the last two? Since Josephus survived, we assume he had worked out the answer.

What the assignment makes of it

The general case — n people, elimination every k — admits no simple formula. The assignment therefore proceeds in two stages:

1. a computational study answering any configuration by simulation;
2. a mathematical study restricted to the case k = 2, where an exact formula exists and can be read off the binary expansion of n.

We write J(n) for the position of the last survivor when n people are eliminated two by two.

The numbering trap

Beware from the outset: people are numbered from 1, whereas Python lists are indexed from 0. Confusing the two shifts every answer by one — the most common mistake on this problem.