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

```
//
// 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! 🖖