xi. Josephus Problem

Problem. $n$ people stand in a circle; counting starts at person $0$, and every $k$-th person is removed. Who survives? (Josephus, 1st century; the CP classic.)

Variant	Method	Cost
any $n,k$	$J(1)=0$, $J(n)=(J(n-1)+k)\mathrm{mod}n$	$O(n)$
huge $n$, small $k$	remove a whole lap ($\lfloor n/k\rfloor$ people) at once	$O(k\log n)$
$k=2$	$J(n)=2(n-2^{\lfloor {\log }_{2}n\rfloor })+1$ (1-indexed): rotate $n$‘s binary representation left by one	$O(1)$
order of elimination	order-statistics tree / BIT: find the next $k$-th alive	$O(n\log n)$
$m$-th eliminated person	the same recurrence on the last $n-m+1$ people	$O(n)$

long long josephus(long long n, long long k) {     // 0-indexed survivor; O(k log n) for large n, O(n) for small n
    if (n == 1) return 0;
    if (k == 1) return n - 1;
    if (k > n) return (josephus(n - 1, k) + k) % n;
    long long r = josephus(n - n / k, k) - n % k;  // one full pass removes n / k people
    if (r < 0) r += n;
    else r += r / (k - 1);
    return r;
}
long long josephus2(long long n) {                 // k = 2, 1-indexed: rotate the binary representation left
    long long h = 1LL << (63 - __builtin_clzll(n));
    return 2 * (n - h) + 1;
}

Proof: the recurrences

Linear. After the first removal (person $k-1$), relabel the remaining $n-1$ people starting from the next one, so label $x$ in the smaller circle is person $(x+k)\mathrm{mod}n$ in the original. The survivor of the smaller circle is $J(n-1)$, hence $J(n)=(J(n-1)+k)\mathrm{mod}n$. Lap jump. For $k\le n$, one lap removes the people at positions $k-1,2k-1,\dots$, i.e. $\lfloor n/k\rfloor$ people, and the next count starts right after the last removed one, at position $k\lfloor n/k\rfloor$. Solve the circle of $n^{\prime }=n-\lfloor n/k\rfloor$ people recursively, then map back: shift by the $n\mathrm{mod}k$ survivors at the end of the lap (which come first in the new circle) and re-insert one removed person for every $k-1$ survivors; this is the r - n % k and r += r / (k - 1) step. Each level shrinks $n$ by a factor $1-1/k$, so the depth is $O(k\log n)$. $k=2$. If $n=2^a+l$ with $0\le l<2^a$, after $l$ removals $2^a$ people remain and the count starts at person $2l$ (0-indexed); for a power of two the starting person survives (each lap halves the circle and keeps the start). So the survivor is $2l+1$ in 1-indexed form. Tested against direct simulation for all $n\le 60$, $k\le 70$.