Err Less (少出错): Finding Josephus

Here’s a JavaScript function that solves the Josephus problem.

function J(n) { return parseInt(n.toString(2).slice(1) + "1", 2); }

Let’s see how and why it works.

If the number of rebels, n, is a power of two, then the rebel at the beginning of the circle (the rebel in position number 1) is the last one standing. Why?
1. If n is even, then on the first pass (i.e. the first time around the circle) all rebels in even-numbered positions are eliminated; hence, the rebel in the first position (one of the odd-numbered positions) is safe for the time being.
2. If n is not only even but is also a power of 2, then the lucky rebel in position number 1 is always safe, because, if we renumber the rebels’ positions after each pass, he is never in an even numbered position at the beginning of any pass. (When n is a power of 2 and there is more than one rebel remaining, there is always an even number of rebels at the beginning of a cycle, since exactly half of the rebels are eliminated each time around. Note that this is not necessarily true if the number of rebels at the beginning of a cycle is odd or if we pass over more than one rebel before eliminating the next one.)
Regardless of whether the number of rebels is a power of two, at some point during the first pass, the number of rebels remaining will be a power of two. (Convince yourself of this crucial fact.) At that point, the rebel at the beginning of that circle will be the last rebel standing.
Let k be the number of rebels that must be eliminated to reduce the number of rebels in the circle to a power of two. The k^th rebel eliminated is the (2k)^th rebel in the circle, since death passes over the first rebel, the second rebel is killed, the third rebel is passed over, the fourth rebel is killed, and so on. Therefore, the rebel at position 2k + 1 will be the rebel at the beginning of a circle with a number of remaining rebels equal to a power of two and will therefore be the last one standing.
We can write n = 2^m + k, where m is the largest integer such that 2^m ≤ n. The last rebel standing is at position 2k + 1. By substituting (n - 2^m) for k, we see that the last rebel standing is at position 2(n - 2^m) + 1.
The “one-bit cycle shift left” trick.
To see how this trick works, we need to pay close attention to a couple of things. First, notice that the value 2^m, as described above, is the value represented by the most significant 1 in the binary representation of the number n. Therefore, the value (n - 2^m) is the number n expressed in binary without the first or “leading” 1 (the most significant digit, assuming the number is not padded with any leading zeros). Second, notice that we can multiply a positive integer by 2 by shifting all the digits of the base two representation of the integer to the left one place and “shifting in” (inserting) a zero in the least significant position of the newly formed number.
The grand finale: We can determine where the historian Flavius Josephus will want to stand in a vicious circle of n suicidal rebels by: expressing n in base 2; dropping the leading or most significant 1 to get the value of k (recall that k ≡ n - 2^m); shifting the result left one place to get the value of 2k; and putting a 1 in the least significant position of the shifted number to get the value of 2k + 1. Neat!

Finally, let’s rewrite the compact JavaScript function shown above as a function composed of a short sequence of simple statements. The following version is more verbose than the previous one, but it’s a little less obscure too. It’s a trade-off.

function J(n) { // Consider the case where n is 41 (base 10).
  let nB2 = n.toString(2); // The number 41 is 101001 in base 2.
  let tail = nB2.slice(1); // We slice off the first 1, leaving 1001.
  let newB2 = tail + "1"; // We shift left and add 1 to get 10011.
  let j = parseInt(newB2, 2); // The number 10011 is 19 in base 10.
  return j; // So 19 is the Josephus number when n is 41.
}
alert(J(41)); // Voila!

Err Less (少出错)

Pages

Finding Josephus

See Also