The Josephus Problem in JavaScript

The problem is named after Flavius Josephus, a Jewish historian living in the 1st century. According to Josephus’ account of the siege of Yodfat, he and his 40 soldiers were trapped in a cave by Roman soldiers. 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.

People are standing in a circle 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.

For our solution:

- The point where the executions begin will be at 12 o’clock if we distribute all the people evenly over a circle.

- The direction is clockwise

- The number of skips is 0, meaning person 1 kills the person immediately to their left.

Let’s try with 9 people.

n = 9;

k(n) = 3;

because, given

1,2,3,4,5,6,7,8,9

1 kills 2

3 kills 4

5 kills 6

7 kills 8

Remaining are:

1,3,5,7,9

we now start at 9 because 1 is next to 9 if the numbers are arranged in a circle.

9 kills 1

3 kills 5

Remaining are:

9,3,7

We now start at 7

7 kills 9

Remaining are:

3, 7

3 kills 7

The winner is number 3

Let’s write some code to do this for us.

See the Pen The Josephus Problem by Amando Abreu (@amando96) on CodePen.

Feel free to change the input and even feel free to change the code, I’ve included a simple test case.

This is a list of the input n(number of people) and output k(n)(which number survives) from 1 to 100.

You can see some patterns start to emerge, and it seems like 1 appears at specific intervals.

k(n) = 1 shows up at n = 1,2,4,8,16,32,64.

If you know binary, you know what these numbers mean. They can be expressed as such:

1 = 2⁰; 2 = 2¹; 4 = 2²; 8 = 2³; 16 = 2⁴; 16 = 2⁵; 32 = 2⁶; 64 = 2⁷.

128 is out of bounds for this data set, but if we run the function with n = 128(2⁸), we should get k(128) = 1.

After changing the input of our function, we indeed got k(128) = 1, why is that? Does it repeat forever?

Let’s try the first 100 2^a. But wait, these numbers get very big very fast. Javascript can handle a maximum array size of 2³²-1 according to the ECMA-262 5th Edition specification due to being bound by an unsigned 32-bit integer due to the ToUint32 abstract operation, so the closest power of two we can try is 2³¹. But my browser crashes.

The biggest I can do in a few seconds is 2¹⁵ = 32768. And it’s true, it’s equal to 1.

So we can say that

if n = 2^a

then k(n) = 1.

When doing this exercise manually it was less obvious, but the way I built the code made it more obvious as to why.

In JavaScript, array keys start at 0. For everyone to kill the person to their left starting with person 1, is the same as filtering out/eliminating every person in a key whose modulo is equal to 0.

…. to be continued

• Previous Article

  Lisp: Day 0

• Next Article

  How To: Enumerate WordPress Users(and how to fix it)