Josephus Problem

The Josephus problem $J(n, k)$ has a linear time solution over all valid $k$ . However, this is too slow, as the number given in the problem statement is about $2^{61}$ . For the special case of $k=2$ , however, there exists a solution with greatly improved running time. By removing the most significant bit (MSB), shifting the number 1 to the left, and readding the MSB at the beginning, we obtain the answer for $J(n, 2)$ . Convince yourself this works on the sample case given for $n=5$ . The code is then a matter of implementation. Sample is given in C++ below.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

#include <iostream>

using namespace std;

int main() {
    long long n = 1234567890193245123;
    long long n2 = n;
    long long i = 0;
    while (1) {
        n2 >>= 1;
        if (!n2)
            break;
        i++;
    }
    cout << (((n & ~(1LL << i)) << 1LL) | 1LL) << endl;
}

Probably the most elegant solution I know for this problem is using the binary form of the number: For a given n, We convert n to binary, so that it looks like 1b1b2...bm and then we shift the first 1 to the right by a cyclic shift so that now we have b1b2...bm1 in binary form. Let this binary number have the decimal equivalent as d. Then the survivor is d. For those interested, you can read about it on Wikipedia. Its given quite nicely there. Also for a given n, there is an explicit formula, (2(n-2^floor((ln(n)/ln(2))))+1) th person is the survivor.

More generally, $n$ people stand in a circle. Starting from the first person, every second person is eliminated from the circle. Who is the last remaining person? For the case where $n$ is not a power of 2, we write $n$ as $n = 2^m + k$ , where $2^m$ is the largest power of 2 less than or equal to $n$ , and solve for $k$ ; $k$ people must be eliminated to reduce the problem to a power of 2, which means that $2k$ people must be passed over, and thus person $2k+1$ will be the survivor.

Applying this general solution for $n$ people standing in a circle to the case of 1234567890193245123 people standing in a circle: the closest power of 2 to 1234567890193245123 is $2^{60}$ . So we have the equation 1234567890193245123 = $2^{60} + k$ . Solving for $k$ , we get that $k$ = 81646385586398147, and thus the last remaining person is person 2(81646385586398147) + 1 = 163292771172796295.