How does printing Josephus sequence work?

Question

The CSES problem Josephus Problem I requires us to print the sequence of how people are chosen for n people and k = 2. I found an elegant solution to this here. Basically, the code is similar to this:

void J(int n)
{
    int a = 1, b = 0;
    while (n > 0)
    {
        for (int i = 2; i <= n; i += 2)
        {
            cout << a * i + b << ' ';
        }
        if (n & 1)
            cout << a + b << ' ', b += a;
        else
            b -= a;
        a <<= 1;
        n >>= 1;
    }
}

Can someone explain why it works?

Answer 1

I made a few changes to the code to illustrate how it works.

void J(int n)
{
    int a = 1, b = 0;
    while (n > 0)
    {
        std::cout << "n=" << n << std::endl;
        std::cout << "a=" << a << ", b=" << b << std::endl;
        for (int i = 2; i <= n; i += 2)
        {
            std::cout << a * i + b << ' ';
        }

        if (n & 1) // equivalent to n % 2 == 1 (if n is odd)
            std::cout << '*' << a + b << ' ', b += a;
        else
            b -= a;
        
        std::cout << std::endl;
        a <<= 1; // a = a * 2;
        n >>= 1; // n = n / 2;
    }
}

The first thing to note is that the variables a and b are initialized to values that allow us to compute the positions of people who will be eliminated as we go around the circle (also using the iterator i in the for loop). The initial values of a = 1, b = 0 are so we can eliminate every even numbered person on the first iteration.

Next, every time through the while(n) loop, half of the remaining people will be eliminated. If n is odd, we loop back to the beginning of the circle and also eliminate the person at the start of the current iteration.

I think the tricky part here is how the values of a and b change in the if statement. If n is odd we increment b by the value of a. If n is even we subtract the value of a from b. Then we double the value of a to get ready for the next iteration around the circle. The values of a and b are chosen to account for the gaps in the circle left by eliminating positions in the previous iterations.

Finally, we divide n by 2 before the next iteration, since there are half as many people left in the circle. Here's a sample run for n=19.

Output:

n=19
a=1, b=0
2 4 6 8 10 12 14 16 18 *1
n=9
a=2, b=1
5 9 13 17 *3
n=4
a=4, b=3
11 19
n=2
a=8, b=-1
15
n=1
a=16, b=-9
*7