I saw this interesting problem on The Daily WTF the other day:

Josephus and forty of his fellow soldiers retreated from the siege of Yodfat to a small cave in the hills. Surrounded by the Roman legion with no chance of escape, the soldiers saw no other choice but to commit suicide. Like the people of Masada, they would rather die than face capture.

In order to decide who would die in which order, the soldiers stood in a circle and, starting with the top of the circle and continuing clockwise, counted to three. The third man got the axe and the counting resumed at one. The process continued until there was no one left. Josephus, who didn’t quite agree with the whole “we should all kill ourselves” idea, figured out the perfect way to avoid death: be the last man standing.

Of course, the above illustration has only twelve men, and Josephus somehow managed to figure out very quickly where to stand with forty others.

It was posed as a programming riddle, but I think it’s a very cool mathematical riddle too.

As a programmer, the simplest way to solve it is to write a function that basically goes through the whole process, killing off the virtual “soldiers” until you’re left with the sweet spot. With the speed of today’s computers, that makes perfect sense.

But I was wondering how Josephus solved the problem himself. The programming approach would be akin to him drawing all the forty soldiers on a sheet of paper, and then crossing them off one by one until he figured out which one would be left standing last. Definitely doable, but it might take a while.

So my question to you is… can you think of any mathematical shortcuts to quickly figure out where the safe spot is?

(You have two variables. The number of soldiers, and how many soldiers to skip in each step. Have fun!)

1. da bishop Says:
   April 24th, 2011 at 5:40 am

   Use bases.

   Mmm.

   This is recursive.

   Well, I suppose one would just work backwards, and generate it from Mr. Survivor outwards.