The Josephus Problem: Background

In Herstein and Kaplansky's wonderful book Matters Mathematical (Chelsea Publishing, 1978), the following legend about the famous first-century historian Flavius Josephus is recounted:
In the Jewish revolt against Rome, Josephus and 39 of his comrades were holding out against the Romans in a cave. With defeat imminent, they resolved that, like the rebels at Masada, they would rather die than be slaves to the Romans. They decided to arrange themselves in a circle. One man was designated as number one, and they proceeded clockwise killing every seventh man... Josephus (according to the story) was among other things an accomplished mathematician; so he instantly figured out where he ought to sit in order to be the last to go. But when the time came, instead of killing himself he joined the Roman side.
The solution is for Josephus (so-called because of the obvious snickering caused by saying "Flavius'' out loud --- try it and see) to stand in the twenty-fourth position. It is yet another historical example of how those with a distaste for mathematics quickly become the chaff of evolution. That point aside, the problem rightfully raises the question of how someone might be able to quickly compute the correct place to stand. This scenario is actually very similar to the methods that children often use to decide things on the playground. We can almost imagine the Roman soldiers singing (but in Latin, of course), "One potato, Two potato, Three potato, Four; Five potato, Six potato, Seven potato, More." On the "More," someone would be eliminated, and the count is done again, with the process repeated until only one person is left. This sort of problem remained the subject of puzzle problems for hundreds of years, until Leonhard Euler wrote a paper called (but in Latin, of course), "Observations on a new and singular type of progression," bringing the Josephus Problem into the framework of analysis of recursively described sequences of numbers.  Today the problem is used to build recursive reasoning skills through exploration.
The activities on this is page allow you to interactively explore the elimination order of n people where every kth person is killed.