The Josephus Problem

The final problem presented in the first chapter of Concrete Mathematics: A Foundation for Computer Science is The Josephus Problem. While the fables of the origin of this problem are entertaining in themselves, the premise itself is simple. We have n objects that are given sequential labels from 1 to n, and arranged in a circle in the same sequence. Starting from the object labeled 1, we are to eliminate every second object until only one object survives. The objective is to determine the label associated with the surviving object.

As an example, consider the Josephus number J(n) for n = 12, shown in the diagram above. Labels get eliminated in the following sequence:

2, 4, 6, 8, 10, 12, 3, 7, 11, 5, 1

…leaving 9 at the very end.

J(12)=9

In looking for a general solution to this problem, we first observe that the pattern of elimination is slightly different depending on whether n is even or odd. When n is even, the first round eliminates all even numbers. The second round begins again with 1, but with exactly half the original number of objects, but with the labels themselves being larger. We can establish the following relation:

J(2n) = 2J(n)\;-\;1 \tag{1}

When n is odd, the first round again eliminates all even numbers, but the second round begins by eliminating 1. Similar to equation (1), we can establish the following relation:

J(2n + 1) = 2J(n) + 1 \tag{2}

With these recurrence relations established, we can calculate a few sample values of the function and thereby derive a general proposition.

\begin{aligned}
J(1) &= 1 \\ \\
J(2) &= 1 \\
J(3) &= 3 \\ \\
J(4) &= 1 \\
J(5) &= 3 \\
J(6) &= 5 \\
J(7) &= 7 \\ \\
J(8) &= 1 \\
J(9) &= 3 \\
J(10) &= 5 \\
J(11) &= 7 \\
J(12) &= 9 \\
J(13) &= 11 \\
J(14) &= 13 \\
J(15) &= 15 \\ \\
J(16) &= 1
\end{aligned}

\begin{aligned}
J(2^m + l) &= 2l + 1 & 0 \le m, 0 \le l \lt 2^m \tag{3}
\end{aligned}

Proof (by induction on m)

We already know the value of the function when n=1, which we obtain when m = l = 0.

\begin{aligned}
J(1) = J(2^0 + 0) = 1 \tag{4}
\end{aligned}

Suppose that the proposition is true for some m \ge 0. We want to show that this implies that the proposition is also true for m + 1. To do so, we need to examine two cases separately: (a) when l is even, and (b) when l is odd.

\begin{aligned}
\text{(when $l$ is even)} \\ \\
J \big(2^{m+1}+l\big) &= J \big(2 \cdot [2^m+l/2]\big) \\
                        &= 2 \cdot J (2^m+l/2)-1 \\
                        &= 2 \cdot (2 \cdot l/2 + 1)-1 \\
                        &= 2l + 1 \\
\\
\text{(when $l$ is odd)} \\ \\
J \big(2^{m+1}+l\big) &= J \big(2 \cdot [2^m+(l-1)/2] + 1\big) \\
                        &= 2 \cdot J \big(2^m+(l-1)/2\big) + 1 \\
                        &= 2 \cdot \big(2 \cdot (l-1)/2 + 1\big) + 1 \\
                        &= 2l + 1 \\
\end{aligned}

These results follow from the earlier recurrence equations (1) and (2) and the assertion that the proposition is true for a specific m. Together with the base case in (4), they show that the proposition is indeed true for all m. QED.

There are a number of ways to implement this program in Rust, and in this case, we take the most straightforward approach of evaluating the formula (3) that we just proved.

Preparation

• Make sure cargo is installed on your system via rustup.
• Create a new package called hanoi to run your code.

$ cargo new josephus
$ cd josephus

P0: Basic Solution

Link to GitHub branch.

//
// src/lib.rs
//

/// Calculate the Josephus Number J(n) for any n > 0.
///
/// We use a simple formula here: express the number `n` as
/// 2^m + l for some m >= 0, 0 <= l < 2^m, then calculate the
/// value of 2 * l + 1, which is the result.
///
/// * `n` - The number to calculate J for
pub fn josephus(n: u32) -> u32 {
    let base: u32 = 2;

    let mut index: u32 = 0;
    let mut hbits: u32 = n;

    loop {
        hbits = hbits >> 1;
        if hbits == 0 {
            break;
        }
        index += 1;
    }

    let l = n - base.pow(index);

    2 * l + 1
}

#[cfg(test)]
mod tests {

    use super::*;

    #[test]
    fn test_one() {
        assert_eq!(josephus(1), 1);
    }

    #[test]
    fn test_three() {
        assert_eq!(josephus(3), 3);
    }

    #[test]
    fn test_twelve() {
        assert_eq!(josephus(12), 9);
    }

    #[test]
    fn test_fifty_one() {
        assert_eq!(josephus(51), 39);
    }

    #[test]
    fn test_sixty_four() {
        assert_eq!(josephus(64), 1);
    }
}

That’s all for today, folks! 🖖