The Josephus Problem

I originally wrote about the Josephus problem in response to a question from a student about a class of counting out problems. The question, and my response follow:

The emperor has invited you to dinner. It is well known that the
emperor regularly invites a number of guests to dinner and only one
person leaves the dinner as a happy person. You see, the emperor is a
bit "touched" in the head! He invites people to dinner then dumps
oatmeal on top of every other person's head until only one person
remains! The one guest without oatmeal at the end of the meal
receives a million dollars! How can you determine where to sit if you
don't want oatmeal on your head. You won't know how many guests have
been invited to dinner until you arrive. You do know that every
second person will receive the oats, you do know where the emperor
will begin this silly feat with the eager beaver in seat number one!

How would you find a formula for this. Is there a pattern? Please
;help me!

Thank you.


This type of problem is called a "Josephus problem", after a story about a historian of the first century, Flavius Josephus, who survived the Jewish-Roman war perhaps due to his mathematical talents. In his book The Jewish Wars Flavius tells that he was one out of 41 Jewish rebels trapped by the Romans. His companions preferred suicide to escape, so they decided to draw lots to see who would kill whom so that they could avoid both capture and the sin of suicide. The idea that they decided to form a cycle and to kill every third person and to proceed around the circle until no one was left is probably a myth. According to the problem Josephus wasn't excited by the idea of killing himself, so he calculated where he has to stand to survive the vicious circle. The general Josephus problem; involves how many people will stand around a circle and how many shall be passed over before the next one is killed (or in your case, have oatmeal dumped on their head).

The reference comes from Book 3, Chapter 8, par 7 of Josephus' The Jewish War (writing of himself in the third person):

However, in this extreme distress, he was not destitute of his usual sagacity; but trusting himself to the providence of God, he put his life into hazard [in the manner following]: "And now," said he, "since it is resolved among you that you will die, come on, let us commit our mutual deaths to determination by lot. He whom the lot falls to first, let him be killed by him that hath the second lot, and thus fortune shall make its progress through us all; nor shall any of us perish by his own right hand, for it would be unfair if, when the rest are gone, somebody should repent and save himself." This proposal appeared to them to be very just; and when he had prevailed with them to determine this matter by lots, he drew one of the lots for himself also. He who had the first lot laid his neck bare to him that had the next, as supposing that the general would die among them immediately; for they thought death, if Josephus might but die with them, was sweeter than life; yet was he with another left to the last, whether we must say it happened so by chance, or whether by the providence of God. And as he was very desirous neither to be condemned by the lot, nor, if he had been left to the last, to imbrue his right hand in the blood of his countrymen, he persuaded him to trust his fidelity to him, and to live as well as himself.

Some while after I responded to the letter above, I sent a note to the Historia Matematica discussion list and Albrecht Heeffer graciously answered to tell me a little more about the history of this problem. Here is his answer, interlaced with my questions:

ME: First, is it essentially correct that Cardan created or first wrote the story of Josephus into the problem?

AH: Yes! Probably the most extensive study on the history of the "Christians and Turks problem" is by Wilhelm Ahrens (1901). It is Ahrens who stated that Cardan was the first to use Josephus as the last man and to name the problem "ludus Josephi" (p. 287-8). No instances of the name 'Josephus game' were found prior to Cardan's "Practica Arithmeticae generalis" of 1539 (see Tropfke 1980 and Singmaster 2002). I traced and checked several sources as well.

ME: Is there record of alternative versions of the problem prior to  Cardan, and where, how early, and in particular, how early do we have  recorded evidence of children's counting games for elimination?

AH: The problem was very popular during the 15th and 16th century. It appears in many arithmetics books under different variations: christians and jews (Buteo), Franciscans and Camoldensians (Calandri, c. 1500), students and rascals (Ben Ezra, c. 1150). The problem, under the same form was know to the Arabs. Singmaster( See below) quotes several Japanese sources from the 12th century and later. Singmaster also refers to a study by Gerard Murphy (1942) who found several Latin sources dealing with the problem before the 10th century. Murphy claims the problem is of Irish origin from the 9th century!Children's counting games must have existed already much earlier. 

And here is an excerpt from a note by David Singmaster

It appears in the Japanese literature as early as 1627 (This is in the Jinko-Ki of Yoshida), with 15 children and 15 stepchildren counted by 10s, but with one child (the 15th) skipped, until only one is left. Ahrens cites some indications that it may go back to the 11C in Japan and believes that the problem arose independently in Japan. Takagi has sent me an article by Shimodaira (source and date not given) on the recreational problems in Jing_ki, but this doesn't indicate the date of the second edition which first contained these problems. Shimodaira states the Japanese name of the problem, Mamakodate, first occurs in the essay Tsurezuregusa by Kenk_ Yoshida (1283-1350), but it's not clear if the problem itself is given there. Shimodaira gives the problem in the form where the 15th stepchild protests that he is about to be eliminated and the stepmother agrees to restart from him. Ahrens says that Jing_ki has the stepmother doing this by accident and the bit about the 15th stepchild first occurs in Miyake Kenry, 1795. (In the image below, from Smith/Mikami, the children of each wife are marked in different colored clothing.)  Is there any Chinese material on this problem? I have recently seen an article which claims an Irish origin of the problem, c800, and which gives early medieval forms called the Ludus Sancti Petri. It is often thought to derive from the Roman practice of decimation. Murray's History of Chess mentions 10 diagrams of this in an Arabic chess MS of c1370, possibly referring to a c1350 work. Murray asserts the problem is of Arabic origin. Wakoku Chie-kurabe shows a version with 8 and 8 counted by 8s, such that either group can be the group counted out first!, depending on where one starts.

Is there a pattern? Yes, let's look. If the first "dump" is on head number one then we know that for N guests :
N Best seat Order of elimination
2 2 1
3 2 1,3
4 4 1,3,2
5 2 1,3,5,4
6 4 1,3,5,2,6
7 6 1,3,5,7,4,2
8 8 1,3,5,7,2,6,4
9 2 1,3,5,7,9,4,8,6
10 4 1,3,5,7,9,2,6,10,8
I hope I did all those correctly, I would think you can continue.


If you start with every other one and dump on the second instead of the first, then the numbers of the survivors for a group of n would be
n ---2---3---4---5---6---7---8---9---10--11--12--13--14--15--16--17--18
S ---1---3---1---3----5--7---1---3---5----7----9---11--13--15--1---3---5
Notice that for any power of two, one is the safe place, and for a number 2n + c the best place is 2c+1 (C of course, must be less than 2n).

If you start counting from number one and eliminate every nth person starting with person number "n", the sequence of best places to stand can be found by using modular arithmetic (what many students learn in school as clock arithmetic).. For example, if you eliminate every third person, you can use trial and error to find out that for two poople the best place to stand is position 2. After that, the best place to stand can be found by adding three to the previous best position, with the restriction that if the new position is higher than the number of people simply reduce the position number by n.

N people Best position
2 ---------- 2
3 ---------- 2+3=5 ---- 5-3 = 2
4 ---------- 2+3=5 ---- 5-4 = 1
5 ---------- 1+3=4
6 ---------- 4+3=7 --- 7-6=1
7 ---------- 1+3 = 4
8 ---------- 4+3=7
9 ---------- 7+3=10 --- 10-9=1
10----------- 1+3=4
11 ---------- 4+3=7
12 ---------- 7+3=10
13 ---------- 10+3= 13
14 ---------- 13+3=16 --- 16-14=2

It would seem, then, that for eliminating every fifth person the best positions would be (starting with n=2) at positions number 2, 1, 2, 2, 1, 6, 3, etc...

More detail about the mathematics of the problem is available at Wikipedia, and many other sources.
An Applet to perform the counting out, as well as some wonderful math is also available at the wonderful Cut-The-Math web site.