Four (a binary calculation method)

---

All posts in this series:

• One Potato: A description of the problem
• Two potato: The basic equations
• Three potato: An algebraic formula for the last person left
• Four: A neat calculation method using binary numbers
• Five potato: F# functions to check the various formulae
• Six potato: Using a calculation graph to see the pattern
• Seven potato: Generalizing to other intervals
• More: An efficient algorithm for arbitrary intervals
• Online research: In which I discover that it is called the Josephus problem

---

Introduction

In my first three posts in the series I derived Mathematical formulae for calculating the last person left in a circle if every second person is asked to leave (continuing until only one person remains).

In this post I am going to show a really neat way of calculating the answer. It is based on the binary number representation of the number of people in the circle.

If you are unfamiliar with the binary number system, then I suggest looking for a basic tutorial on binary numbers first.

---

The binary calculation rule

Take the binary representation of the number of people in the circle. Move the left-most (non-zero) bit to the end. Convert back to decimal and you have the number of the last person left.

---

Some examples

$$ f(\underbrace{10}_{\text{decimal}}) = f(\underbrace{1010}_{\text{binary}}) = \underbrace{0101}_{\text{binary}} = \underbrace{5}_{\text{decimal}} $$ $$ f(\underbrace{13}_{\text{decimal}}) = f(\underbrace{1101}_{\text{binary}}) = \underbrace{1011}_{\text{binary}} = \underbrace{11}_{\text{decimal}} $$

---

Derivation

In my third post of the series I derived an algebraic formula for the last person left in the circle: $$ f(n) = 2n + 1 - 2^{{\lfloor log_2 n \rfloor} + 1} \tag{9} $$ I'd like to write that formula slightly differently: $$ f(n) = 2(n - 2^{\lfloor log_2 n \rfloor} ) + 1 \tag{10} $$

$2^{\lfloor log_2 n \rfloor}$ is just the highest power of 2 that is less than (or equal to) the number. Now each position in a binary representation represents a power of 2. So this represents the left-most bit in the binary representation of n (and all other positions zero).

Then $n - 2^{\lfloor log_2 n \rfloor}$ is just the original number n with its first (non-zero) binary digit dropped (i.e. replaced with a zero). Let's call this number m.

In binary, you can multiply a number by 2 by shifting all its bits one place to the left. So 2m+1 is just a "left shift" of m and set the rightmost bit to 1.

So we can express the binary method as:

• take the binary representation of the number
• drop the leading digit
• append a 1 (i.e. shift left and add 1)
• convert back to decimal

But since we are dropping the leading 1, and appending a trailing 1, you could see this as rotating the first bit around to the end.

---

Next time

In the next post in the series, I will be writing code to calculate the answer using each of the methods presented in the first four posts.

---