Flavius Josephus was a Jewish historian of the first century. Legend has it that he was one of a group of 41 Jewish rebels who decided to kill themselves rather than surrender to the Romans, who had them trapped. They decided to form a circle and to kill every third person until no one was left. Josephus, not wanting to die, calculated where he needed to stand so that he would be the last one alive and thus would not have to die. Thus was born a class of problems referred to as the Josephus problem. These problems involve finding the order of events when events in a list are not taken in order but, rather, they are taken every ith element in a cycle until none remains. For example, suppose that we have a list of seven elements numbered from 1 to 7: 1 2 3 4 5 6 7 If we were to remove every third element from the list, the first element to be removed would be number 3, leaving the list 1 2 4 5 6 7 The next element to be removed would be number 6, leaving the list 1 2 4 5 7 Demonstrates the use of an indexed list to solve the Josephus problem.
Flavius Josephus was a Jewish historian of the first century. Legend has it that he
was one of a group of 41 Jewish rebels who decided to kill themselves rather than
surrender to the Romans, who had them trapped. They decided to form a circle and
to kill every third person until no one was left. Josephus, not wanting to die, calculated where he needed to stand so that he would be the last one alive
and thus would not have to die. Thus was born a class of problems
referred to as the Josephus problem. These problems involve finding
the order of events when events in a list are not taken in order but,
rather, they are taken every ith element in a cycle until none remains.
For example, suppose that we have a list of seven elements
numbered from 1 to 7:
1 2 3 4 5 6 7
If we were to remove every third element from the list, the first element to be
removed would be number 3, leaving the list
1 2 4 5 6 7
The next element to be removed would be number 6, leaving the list
1 2 4 5 7
Demonstrates the use of an indexed list to solve the Josephus problem.
Step by step
Solved in 2 steps
