Write Up on
Josephus Problem
- Varun Gupta
(Enrolment Number: cs21btech11060)
What is Josephus Problem?
The Josephus problem is a very interesting problem related to combinatorics. Let’s see the
background of this problem first.
Background
Flavius Josephus was a Jewish-Roman historian from the 1st century. In the Jewish revolt
against Rome, he with his 40 comrades were trapped by Romans in a cave. They decided to
die rather than surrender to Roman, hence they decided a method for such execution. They
arranged themselves in a circle, and designated as number one, two, so on till forty and then
in a clockwise fashion, they killed every 3rd man starting from the 1st. Josephus figured where
to stand to be the last one to be left, and then instead of killing himself, he joined the Roman
side.
This was the story behind the origin of the Josephus Problem.
The generalized Josephus problem statement is as follows:
“Given n people numbered 1..n in a circle waiting to be executed. Starting with the first
person, we eliminate every kth person in a circular manner until only 1 survivor is left. Given
the values of n and k, design an efficient algorithm to find the survivor’s number J(n, k) in the
initial circle.”
Example
Firstly, let’s go through the above original case, the sequence of person executed will be as
follows:
3 ,6 ,9 ,12 ,15 ,18 ,21 ,24 ,27 ,30 ,33 ,36 ,39 ,1 ,5 ,10 ,14 ,19 ,23 ,28 ,32 ,37 ,41 ,7 ,13 ,20 ,26
,34 ,40 ,8 ,17 ,29 ,38 ,11 ,25 ,2 ,22 ,4 ,35
Hence, the person left at last will be at position 31.
So, we can say Josephus (41,3) or J (41,3) = 31, where J is the function which takes value of
n & k respectively and returns the person left at last.
Solutions to Josephus Problem:
Now, let’s dive into the solution of this problem using various different areas of discrete
mathematics.
Case 1 : General Solution using Dynamic Programming
In this approach, we will construct a recursion for J(n, k) and then solve it via dynamic
programming (the programming language used here is C++).
To construct such recursion, let’s dive into logical arguments, when there are n persons and
we have to skip k persons during their execution, after one execution, we would be left with
n-1 persons but now ((k+1) mod n)th person will kill the next person. Now, the problem is to
find J (n-1, k) but with a shift in the position of (k mod n) + 1.
So, the recursion hence obtained is:
Hence, the program will be as follows:
Case 2: Special Case for k = 2
A pattern can be noticed for k = 2, the first 16 values are shown below:
• Firstly, the value of J(2p) ∀ p ∈ N is 1.
• Also, at any power of 2, series of odd number starts and again breaks to 1 for a power
of 2.
Using this pattern, we can formulate a solution for k = 2, first find the nearest power of 2 less
than n, then subtracting both terms find the difference, J (n) = 2*difference + 1.
Let’s take few examples:
• n = 14, nearest power of 2 less than 14 is 8, so diff. = 14-8 = 6. So, J(14) = 2*6+1 =
13.
• n = 41, nearest power of 2 less than 41 is 32, so diff. = 41-32 = 9. So, J(41) = 2*9+1
= 19.
This result can be written mathematically as:
A trick to solve for k = 2,
Using bitwise operator for this case is the easiest approach for Josephus problem. For this,
just shift the most significant bit of n to least significant position to get J(n,2).
For example,
n = 1110 in base 2 i.e., 14 in base 10, then J(n) = 1101 in base 2 i.e., 13 in base 10.
Case 3: Closed form for k = 3
A general proof was given by Lorenz Halbeisen and Norbert Hungerbuhler in 1997, here only
closed form expression for k = 3 is explained.
The equations are as follows:
Let’s take an example to verify this result,
Example: J (41,3)
Bibliography
• Josephus problem – Wikipedia
[Link]
• The Josephus Game
[Link]
• josephus_problem.pdf
[Link]
• The Josephus Problem – Numberphile
[Link]
• Josephus Problem – InterviewBit
[Link]
• Formulae – Josephus problem
[Link]
• The Josephus problem
[Link]