The Josephus Problem in JavaScript

  • by Amando Abreu
  • on 15 February 2019

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.

nk(n)
11
21
33
41
53
65
77
81
93
105
117
129
1311
1413
1515
161
173
185
197
209
2111
2213
2315
2417
2519
2621
2723
2825
2927
3029
3131
321
333
345
357
369
3711
3813
3915
4017
4119
4221
4323
4425
4527
4629
4731
4833
4935
5037
5139
5241
5343
5445
5547
5649
5751
5853
5955
6057
6159
6261
6363
641
653
665
677
689
6911
7013
7115
7217
7319
7421
7523
7625
7727
7829
7931
8033
8135
8237
8339
8441
8543
8645
8747
8849
8951
9053
9155
9257
9359
9461
9563
9665
9767
9869
9971
10073

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 = 20; 2 = 21; 4 = 22; 8 = 23; 16 = 24; 16 = 25; 32 = 26; 64 = 27.

128 is out of bounds for this data set, but if we run the function with n = 128(28), 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 2a. But wait, these numbers get very big very fast. Javascript can handle a maximum array size of 232-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 231. But my browser crashes.

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

So we can say that

if n = 2a

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

About the author

Amando Abreu is a serial entrepreneur, Fractional CTO, and engineer who has been involved in several startups and launched dozens of products. He has worked with companies such as trivago, Portugal Telecom, and Vizrt. He has experience in several industries, most notably e-commerce, SaaS, media, travel, insurance, property development, and construction.
No comments, just