Josephus Problem

Hi, everyone, I’m back again with one of the famous problems in computer science, also in maths and cryptography, it is based on an ancient tale it is the “Josephus Problem”.

Flavius Josephus was a Jewish historian of the 1st century the story goes like this, he and his 40 soldiers were trapped in a cave by Roman soldiers, and all the Jews decided suicide over surrender,

So everybody stood in a circle creating a circle of 41 people, starting from 1 each person is going to kill the person who is standing next to him, it will go like 1 kills 2, 3 kills 4, 5 kills 7 and in the first round the observation is all the even-numbered people are killed,

In the second round, 41 kills 1, 3 kills 5, so every third person is getting killed,

In the third round, every fourth person gets killed, and so on, and at the last 19th soldier Flavius Josephus was left and he didn’t kill himself he surrendered to the Romans.

So here are a few observations regarding this problem, if the number of people is a power of 2, the person who starts is going to win.

For example, if there are 8 people, starting from 1, 1 kills 2, 3 kills 5 at the last number 1 is left.

So the claim is every 2^a + L, the survivor is 2L+1,

13= 2^4 +5, L= 5

2*5+1=11, and number 11 is the survivor.

So, among 41 soldiers, 41=2^5 + 9, 2*9 +1 =19

Another observation is if we write the number 41 in binary notation it would be 101001, if we put the first digit at the last it would be 010011 and if we will convert it into decimal it would be 19. This observation was made by Daniel Erman at the University of Wisconsin-Madison some six years ago.

The solution to this is achievable by implementing the queue data structure,

I have used the template queue available in C++, in which we are just eliminating the numbers or popping them out in an iterative manner.

So this was all, it fascinated me a lot that's why I shared it, next time I will come up with something different.