In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
and
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, the Josephus problem (or Josephus permutation) is a theoretical problem related to a certain
counting-out game
A counting-out game or counting-out rhyme is a simple method of 'randomly' selecting a person from a group, often used by children for the purpose of playing another game. It usually requires no materials, and is achieved with spoken words or hand ...
.
A number of people are standing in a
circle
A circle is a shape consisting of all points in a plane that are at a given distance from a given point, the centre. Equivalently, it is the curve traced out by a point that moves in a plane so that its distance from a given point is const ...
waiting to be executed. Counting begins at a specified point in the circle and proceeds around the circle in a specified direction. After a specified number of people are skipped, the next person is executed. The procedure is repeated with the remaining people, starting with the next person, going in the same direction and skipping the same number of people, until only one person remains, and is freed.
The problem—given the number of people, starting point, direction, and number to be skipped—is to choose the position in the initial circle to avoid execution.
History
The problem is named after
Flavius Josephus
Flavius Josephus (; grc-gre, Ἰώσηπος, ; 37 – 100) was a first-century Romano-Jewish historian and military leader, best known for ''The Jewish War'', who was born in Jerusalem—then part of Roman Judea—to a father of priestly d ...
, a Jewish historian living in the 1st century. According to Josephus' account of the
siege of Yodfat
The siege of Yodfat ( he, יוֹדְפַת, also Jotapata, Iotapata, Yodefat) was a 47-day siege by Roman forces of the Jewish town of Yodfat which took place in 67 CE, during the Great Revolt. Led by Roman General Vespasian and his son Titus, ...
, he and his 40 soldiers were trapped in a cave by
Roman soldiers
This is a list of Roman army units and bureaucrats.
*'' Accensus'' – Light infantry men in the armies of the early Roman Republic, made up of the poorest men of the army.
*'' Actuarius'' – A military who served food.
*''Adiutor'' – A camp o ...
. They chose suicide over capture, and settled on a serial method of committing suicide by drawing lots. Josephus states that by luck or possibly by the hand of God, he and another man remained until the end and surrendered to the Romans rather than killing themselves. This is the story given in Book 3, Chapter 8, part 7 of Josephus' ''
The Jewish War
''The Jewish War'' or ''Judean War'' (in full ''Flavius Josephus' Books of the History of the Jewish War against the Romans'', el, Φλαυίου Ἰωσήπου ἱστορία Ἰουδαϊκοῦ πολέμου πρὸς Ῥωμαίους ...
'' (
writing of himself in the third person):
The details of the mechanism used in this feat are rather vague. According to James Dowdy and Michael Mays, in 1612
Claude Gaspard Bachet de Méziriac Claude may refer to:
__NOTOC__ People and fictional characters
* Claude (given name), a list of people and fictional characters
* Claude (surname), a list of people
* Claude Lorrain (c. 1600–1682), French landscape painter, draughtsman and etcher ...
suggested the specific mechanism of arranging the men in a circle and counting by threes to determine the order of elimination. This story has been often repeated and the specific details vary considerably from source to source. For instance,
Israel Nathan Herstein
Israel Nathan Herstein (March 28, 1923 – February 9, 1988) was a mathematician, appointed as professor at the University of Chicago in 1951. He worked on a variety of areas of algebra, including ring theory, with over 100 research papers and ov ...
and
Irving Kaplansky
Irving Kaplansky (March 22, 1917 – June 25, 2006) was a mathematician, college professor, author, and amateur musician.O'Connor, John J.; Robertson, Edmund F., "Irving Kaplansky", MacTutor History of Mathematics archive, University of St Andr ...
(1974) have Josephus and 39 comrades stand in a circle with every seventh man eliminated. A history of the problem can be found in S. L. Zabell's ''Letter to the editor'' of the ''
Fibonacci Quarterly
The ''Fibonacci Quarterly'' is a scientific journal on mathematical topics related to the Fibonacci numbers, published four times per year. It is the primary publication of The Fibonacci Association, which has published it since 1963. Its founding ...
''.
Josephus had an accomplice; the problem was then to find the places of the two last remaining survivors (whose conspiracy would ensure their survival). It is alleged that he placed himself and the other man in the 31st and 16th place respectively (for = 3 below).
Variants and generalizations
A medieval version of the Josephus problem involves 15 Turks and 15 Christians aboard a ship in a storm which will sink unless half the passengers are thrown overboard. All 30 stand in a circle and every ninth person is to be tossed into the sea. The Christians need to determine where to stand to ensure that only the Turks are tossed. In other versions the roles of Turks and Christians are interchanged.
describe and study a "standard" variant: Determine where the last survivor stands if there are people to start and every second person ( = 2 below) is eliminated.
A generalization of this problem is as follows. It is supposed that every th person will be executed from a group of size , in which the th person is the survivor. If there is an addition of people to the circle, then the survivor is in the -th position if this is less than or equal to . If is the smallest value for which , then the survivor is in position .
Solution
In the following,
denotes the number of people in the initial circle, and
denotes the count for each step, that is,
people are skipped and the
-th is executed. The people in the circle are numbered from
to
, the starting position being
and the counting being
inclusive.
''k''=2
The problem is explicitly solved when every second person will be killed (every person kills the person on their left or right), i.e.
. (For the more general case
, a solution is outlined below.)
The solution is expressed recursively. Let
denote the position of the survivor when there are initially people (and
).
The first time around the circle, all of the even-numbered people die.
The second time around the circle, the new 2nd person dies, then the new 4th person, etc.; it is as though there were no first time around the circle.
If the initial number of people was even, then the person in position during the second time around the circle was originally in position
(for every choice of ). Let
. The person at
who will now survive was originally in position
. This yields the recurrence
:
If the initial number of people was odd, then person 1 can be thought of as dying at the end of the first time around the circle. Again, during the second time around the circle, the new 2nd person dies, then the new 4th person, etc.
In this case, the person in position was originally in position
. This yields the recurrence
:
When the values are tabulated of and
a pattern emerges (, also the leftmost column of blue numbers in the figure above):
This suggests that
is an increasing odd sequence that restarts with
whenever the index ''n'' is a power of 2.
Therefore, if ''m'' and is chosen so that
and
, then
.
It is clear that values in the table satisfy this equation. Or it can be thought that after people are dead there are only
people and it goes to the
th person. This person must be the survivor. So
. Below, a proof is given by induction.
Theorem: If
and
, then
.
Proof: The
strong induction
Mathematical induction is a method for proving that a statement ''P''(''n'') is true for every natural number ''n'', that is, that the infinitely many cases ''P''(0), ''P''(1), ''P''(2), ''P''(3), ... all hold. Informal metaphors help ...
is used on . The base case
is true.
The cases are considered separately when is even and when is odd.
If is even, then choose
and
such that
and
. Note that
.
is had where the second equality follows from the induction hypothesis.
If is odd, then choose
and
such that
and
. Note that
.
is had where the second equality follows from the induction hypothesis. This completes the proof.
can be solved to get an explicit expression for
:
:
The most elegant form of the answer involves the binary representation of size :
can be obtained by a one-bit left cyclic shift of itself. If is represented in binary as
, then the solution is given by
. The proof of this follows from the representation of as
or from the above expression for
.
Implementation: If n denotes the number of people, the safe position is given by the function
, where
and
.
Now if the number is represented in binary format, the first bit denotes
and remaining bits will denote . For example, when , its binary representation is
n = 1 0 1 0 0 1
2
m = 1 0 0 0 0 0
l = 0 1 0 0 1
/**
* @param n the number of people standing in the circle
* @return the safe position who will survive the execution
* f(N) = 2L + 1 where N =2^M + L and 0 <= L < 2^M
*/
public int getSafePosition(int n)
Bitwise
The easiest way to find the safe position is by using
bitwise operators
In computer programming, a bitwise operation operates on a bit string, a bit array or a binary numeral (considered as a bit string) at the level of its individual bits. It is a fast and simple action, basic to the higher-level arithmetic operat ...
. In this approach, shifting the most-significant set bit of n to the least significant bit will return the safe position.
Input must be a positive integer.
n = 1 0 1 0 0 1
n = 0 1 0 0 1 1
/**
* @param n (41) the number of people standing in the circle
* @return the safe position who will survive the execution
*/
public int getSafePosition(int n)
''k''=3
In 1997, Lorenz Halbeisen and Norbert Hungerbühler discovered a closed-form for the case
. They showed that there is a certain constant
:
that can be computed to arbitrary precision. Given this constant, choose to be the greatest integer such that
(this will be either
or
). Then, the final survivor is
:
if is rounded up else
for all
.
As an example computation, Halbeisen and Hungerbühler give
(which is actually the original formulation of Josephus' problem). They compute:
:
:
and therefore
:
(note that this has been rounded down)
:
This can be verified by looking at each successive pass on the numbers through :
:
:
:
:
:
:
:
:
The general case
Dynamic programming
Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics.
I ...
is used to solve this problem in the general case by performing the first step and then using the solution of the remaining problem. When the index starts from one, then the person at
shifts from the first person is in position
, where n is the total number of persons. Let
denote the position of the survivor. After the
-th person is killed, a circle of
remains, and the next count is started with the person whose number in the original problem was
. The position of the survivor in the remaining circle would be
if counting is started at
; shifting this to account for the fact that the starting point is
yields the recurrence
:
which takes the simpler form
:
if the positions are numbered from
to
instead.
This approach has
running time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...
, but for small
and large
there is another approach. The second approach also uses dynamic programming but has running time
. It is based on considering killing ''k''-th, 2''k''-th, ...,
-th people as one step, then changing the numbering.
This improved approach takes the form
:
References
Citations
Sources
*
*
*
*
*
*
*
*
*
Further reading
*
*
*
*
*
*
* FUN2010
*
*
*
*
*
External links
Josephus Flavius game(Java Applet) at
cut-the-knot
Alexander Bogomolny (January 4, 1948 July 7, 2018) was a Soviet-born Israeli-American mathematician. He was Professor Emeritus of Mathematics at the University of Iowa, and formerly research fellow at the Moscow Institute of Electronics and Math ...
allowing selection of every n
th out of 50 (maximum).
*
* {{YouTube, id=uCsD3ZGzMgE, title=The Josephus Problem - Numberphile
Generalized Josephus Problem
Combinatorics
Computational problems
Josephus
Mathematical problems
Permutations