A few years ago, I discovered my passion for stories that have some relationship with Mathematics. I enjoy reading about the genius mathematician that’s ahead of his time and misunderstood by his contemporaries. Let’s face it, it always follows the same trend: their bios rarely end up well.
But there is another type of story: the one which is so lost in time that sounds like an ancient legend. And that’s the one that can let my imagination fly. The Josephus’ story pictured here is the perfect example:
Imagine that you are a general commanding a small unit. Things are not looking good, you and your men are hiding in a cave. It’s dark, you fear for the worst, but at the same time, you order everybody to keep silence. When you hear the footsteps of Roman’s enemy soldiers approaching, you smell blood and realize the end is near. Indeed you are surrounded and — no matter what — you already know what’s coming.
To make things worst: your soldiers have been educated in order to choose self-sacrifice over being taken as hostages. There is no escape, your soldiers are starting to make “the circle” in order to perform the suicide ritual. You cannot trust them with the fact that you will prefer living, even if that means being taken as a prisoner. If you do: you fear a riot, so you need to think fast and choose the correct position in the circle. That’s the only way to beat the ritual and your only possibility to stay alive and surrender.
Yeah, I know it sounds dramatic! But that’s how my brain hooks into these topics. If you want to know more about “the circle” and how the secret ritual works: keep reading.
So to put you back into the situation: there are two options either to be captured or suicide. Your army always prefers not to be captured so they elaborated this weird ritual. The ritual consists of getting your soldiers together in a circle, every man will eliminate the one to its left. Let’s visualize how the iterations, for a unit of 5 men inside that cave:
So in this scenario, the general will clearly prefer to be standing in position 3. So given a group on N soldiers, the question is: In which position of the circle you should place yourself in order to be the last man standing?
At some point, before deciding to start drafting this article I was watching the video about [The Josephus Problem at Numberphile](https://www.youtube.com/watch?v=uCsD3ZGzMgE), the next thing I knew was that my programmer brain already formulated this as a coding challenge. That looks like this:
“Given a number of soldiers N, standing in a circle and considering every soldier will take turns to eliminate the soldier standing to its left — following a clockwise direction. Write a function that receives the number N, and returns the position of the last man standing.”
Without thinking much, I opened the browsers’ DevTools and wrote my first ugly solution:
Why an array? Why not a Set and skip and remove elements from it? Or why not something fancier like a circular linked list? I knew the moment I wrote the inner for loop this thing will be at least n square in terms of Big O. But let’s continue, there is a couple of smart ways to make this O(1).
If we analyze the numeric sequence we can spot some hidden mechanisms. To begin take a look at the number of soldiers, notice for every square quantity the solution is always 1.
NumberOfSoldiers = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, …
Solution = 1, 1, 3, 1, 3, 5, 7, 1, 3, 5, 7, 9, 11, 13, 15, 1, …
NearestLowerSquare = 1, 2, 2, 4, 4, 4, 4, 8, 8, 8, 8, 8, 8, 8, 8, 16, …
NumberOfSoldiers - NearestLowerSquare = 0, 0, 1, 0, 1, 2, 3, 0, 1, 2, 3, 4, 5, 6, 7, 0, …
So we can get a formula, and if you did not see The Josephus Problem Video at Numberphile I recommend you to watch it. So what the video is telling us is that we not have to do all the operations to find the “safe position”. We only need to perform L operations.
We can obtain L by subtracting the higher bit from the 5. We know we can express 5 as 2²*1+2¹*0+2⁰*1, and we know a circle of any power of two will result to be 1. So a circle of 4 soldiers will land us on position 1 which is the same starting point. That’s why we can leave the 4 (or 2²) aside and grab the rest of the binary as L. In this case L is 1 (or 2¹*0+2⁰*1). So L is the number of operations to execute. This translates into soldier on position 1 kills soldier on position 2, and that lands us on soldier 3. Which happens to be in the “safe position” because now that soldier 2 is gone, we have a circle of 4 people.
Let’s take a look at the case where the number of soldiers is 12.
Once we know the L value, we can stop thinking about loops, keeping track of the soldiers standing or concerning about the circular structure. We can simply arrive at the solution by doing 2L + 1.
Sol(n) = 2 * ( n - nearestLowerPow2(n) ) + 1
So how do we calculate the nearest lower square? Which means:
At this point, I had a fuzzy memory about a formula including logarithms so I did a quick StackOverflow search. I’ve found something that is not exactly what we need: Rounding up to the next power of 2, because we need equal or lower power of 2. But that was enough for me to write this second solution.
But hold on, here comes the beauty of Mathematics offering us something more elegant. Because when you start thinking about this problem in terms of binary numbers, this can be even simpler.
Just by following this procedure. Convert the number into binary form. For example, take the 5, into binary will be “101”. Then get the first one in the binary form and position it at the very end, in our case transform “101” into “011”. And back to decimal, you will find your answer to be 3.
That’s all folks. Thanks for joining me in this coding adventure. If you want to dive deep into this bitwise solution I recommend reading [the entry on wikipedia](https://en.wikipedia.org/wiki/Josephus_problem).
If you have a different idea to re-implement solution 1 or want to resolve it using another language please feel free to share it by posting it in the comments. A full Java bitwise implementation can be found here.