A Thinking Ape - Circle problem

General solution

Puzzle

Imagine you have a circle of people and you go around the circle removing every second person until one person is left.

If you have 3 people in the circle, then the 3rd person will be the last one remaining. If you have 4 people then the 1st person will be the last one remaining. If you have 11 people then the 7th person will be the one remaining.

If you have N people in the circle, who will be the last one remaining?

Please formulate your answer as a general solution and not as an algorithm that simulates the problem.

Solution (pdf file attached in the step 2)

The general solution is:

x = (n - 2^floor(log_2(n))) * 2 + 1

where x indicates the remaining person.

Explaining the formula:

You can see the pattern of the arithmetic progression in a common difference of 2 as we can see in the test below:

N = 2 X = 1th
N = 3 X = 3th
N = 4 X = 1th
N = 5 X = 3th
N = 6 X = 5th
N = 7 X = 7th
...
N = 15 X = 15th
N = 16 X = 1th
...
N = 32 X = 1th
N = 33 X = 3th

As you can see, the value of x will be a progression of 2, with a starting value of 1. (1, 3, 5, 7...)
The point is that this progression is restarted to the initial value in every power of 2 as we can see the same values 1 for 2^0, 2^1, 2^2 and so on...

N = 2 X = 1th N = 2¹ ??? Set value 1!!
N = 3 X = 3th

N = 4 X = 1th N = 2² ??? Reset to value 1!!
N = 5 X = 3th +2
N = 6 X = 5th +2
N = 7 X = 7th +2

N = 8 X = 1th N = 2³ ??? Reset to value 1!!
...
N = 15 X = 15th

N = 16 X = 1th N = 2^4 ??? Reset to value 1!!
N = 17 X = 3th +2
N = 18 X = 5th +2

Explaining the formula:

Step 1) 2^floor(log_2(n))

This will result as the maximum power of 2 under the given number n. We need this value to indicate wheter its the beginning of a new progression.