Josephus problem

Such games are used to pick out a person from a group, e.g. eeny, meeny, miny, moe.

In the particular counting-out game that gives rise to the Josephus problem, a number of people are standing in a circle waiting to be 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 is named after Flavius Josephus, a Jewish historian and leader who lived in the 1st century.

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's 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."

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.The details of the mechanism used in this feat are rather vague.

According to James Dowdy and Michael Mays,[2] in 1612 Claude Gaspard Bachet de Méziriac suggested the specific mechanism of arranging the men in a circle and counting by threes to determine the order of elimination.

For instance, Israel Nathan Herstein and Irving Kaplansky (1974) have Josephus and 39 comrades stand in a circle with every seventh man eliminated.

[4] A history of the problem can be found in S. L. Zabell's Letter to the editor of the Fibonacci Quarterly.

[5] As to intentionality, Josephus asked: “shall we put it down to divine providence or just to luck?”[6] But the surviving Slavonic manuscript of Josephus tells a different story: that he “counted the numbers cunningly and so managed to deceive all the others”.

[6][7] Josephus had an accomplice; the problem was then to find the places of the two last remaining survivors (whose conspiracy would ensure their survival).

[8] 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.

Graham, Knuth & Patashnik 1989, p. 8 describe and study a "standard" variant: Determine where the last survivor stands if there are n people to start and every second person (k = 2 below) is eliminated.

If there is an addition of x people to the circle, then the survivor is in the p + mx-th position if this is less than or equal to n + x.

This yields the recurrence If the initial number of people were odd, then person 1 can be thought of as dying at the end of the first time around the circle.

a pattern emerges (OEIS: A006257, also the leftmost column of blue numbers in the figure above): This suggests that

: The most elegant form of the answer involves the binary representation of size n:

Implementation: If n denotes the number of people, the safe position is given by the function

Now if the number is represented in binary format, the first bit denotes

⁠, its binary representation is: The easiest way to find the safe position is by using bitwise operators.

In 1997, Lorenz Halbeisen and Norbert Hungerbühler discovered a closed-form for the case

They compute: This can be verified by looking at each successive pass on the numbers 1 through 41: Dynamic programming is used to solve this problem in the general case by performing the first step and then using the solution of the remaining problem.

remains, and the next count is started with the person whose number in the original problem was

yields the recurrence[12] which takes the simpler form if the positions are numbered from

[citation needed] This improved approach takes the form