When we generate a list of who is left for last (L) based on the number of people in the circle (N), we observe a correlation bewteen those values and the binary representation of N:
| N | L | N (binary) | N' (see below) | |
|---|---|---|---|---|
| 2 | 1 | 10 | 0 | |
| 3 | 3 | 11 | 1 | |
| 4 | 1 | 100 | 00 | |
| 5 | 3 | 101 | 01 | |
| 6 | 5 | 110 | 10 | |
| 7 | 7 | 111 | 11 | |
| 8 | 1 | 1000 | 000 | |
| 9 | 3 | 1001 | 001 | |
| 10 | 5 | 1010 | 010 | |
| 11 | 7 | 1011 | 011 | |
| 12 | 9 | 1100 | 100 | |
| 13 | 11 | 1101 | 101 | |
| 14 | 13 | 1110 | 110 | |
| 15 | 15 | 1111 | 111 | |
| 16 | 1 | 10000 | 0000 | |
| … |
L has a sequence that starts in 1 and increases linearly by steps of 2 (3, 5, 7...) and restarts whenever N reaches a power of 2 (2, 4, 8, 16...).
We can see that, if we remove the most significant bit of N, the resulting number (let it be N') also grows linearly, restarting in 0 whenever N reaches a power of 2, and we can calculate L = N' × 2 + 1.
The value of the most significant bit of N can be calculated by POW2(INT(LOG2(N))).
So we have L = (N - POW2(INT(LOG2(N)))) × 2 + 1.
Assuming:
- INT(x) = ⌊x⌋
- POW2(x) = 2x
- LOG2(x) = log 2 x
Log in or sign up for Devpost to join the conversation.