Josephus problem

From Fōrmulæ wiki
Jump to: navigation, search

This page is a solution to the task Josephus problem in the Rosetta Code, written in Fōrmulæ.

Description (from Rosetta Code)

Josephus problem is a math puzzle with a grim description: prisoners are standing on a circle, sequentially numbered from to .

An executioner walks along the circle, starting from prisoner , removing every -th prisoner and killing him.

As the process goes on, the circle becomes smaller and smaller, until only one prisoner remains, who is then freed. >

For example, if there are prisoners and , the order the prisoners are killed in (let's call it the "killing sequence") will be 1, 3, 0, and 4, and the survivor will be #2.

Task

Given any   ,   find out which prisoner will be the final survivor.

In one such incident, there were 41 prisoners and every 3rd prisoner was being killed   ().

Among them was a clever chap name Josephus who worked out the problem, stood at the surviving position, and lived on to tell the tale.

Which number was he?

Extra

The captors may be especially kind and let survivors free, and Josephus might just have     friends to save.

Provide a way to calculate which prisoner is at any given position on the killing sequence.

Notes

  1. You can always play the executioner and follow the procedure exactly as described, walking around the circle, counting (and cutting off) heads along the way. This would yield the complete killing sequence and answer the above questions, with a complexity of probably . However, individually it takes no more than to find out which prisoner is the -th to die.
  2. If it's more convenient, you can number prisoners from   to   instead.   If you choose to do so, please state it clearly.
  3. An alternative description has the people committing assisted suicide instead of being executed, and the last person simply walks away. These details are not relevant, at least not mathematically.

Solution

We start with two lists. The first one contains initially the prisoners (their number), and the second one contains the kills, and it is initially empty.

On every kill, the number of the killed prisoner is deleted from the first list, and it is (striked out) appended to the second one, in order to show the order of kills.

In order to leave more than one survivor, the cycle is repeated n-s times, where n is the number of prisoners and s is the number of survivors.

At the end, the two lists are retrieved.

Even when Fōrmulæ is 1-based, the list is filled starting with the 0 prisoner, in order to the results can be compared with other languages (mostly 0-based).

JosephusProblemProgram.png

Case 1. Given example

5 prisoners, killing every 2:

JosephusProblemCase1.png

Case 2. Task

41 prisoners, killing every 3:

JosephusProblemCase2.png

Case 3. Extra

The same as the previous case, but leaving 3 survivors:

JosephusProblemCase3.png

Much larger example. 23,482 prisoners, killing every 3,343, leaving 3 survivors. Only the survivors are shown (the first element of the resulting list is extracted):

JosephusProblemCase4.png

Additional stuff. Drawing history

The following function creates a raster graphics of size n squares width, and n + 1 squares height, where n is the number of prisoners. The size of the square is defines as pixels.

The horizontal axis (right to left) is the number of the prisoner. The vertical axis (top to bottom) is the number of cycle.

A live prisoner is drawn as green, a dead one is drawn as black.

JosephusDrawing01.png

Drawing for the case 5 prisoners, killing every 2 (cell size 20x20 pixels):

JosephusDrawing02.png

Drawing for the case 41 prisoners, killing every 3 (cell size is 5x5 pixels):

JosephusDrawing03.png

Drawing for the case 500 prisoners, killing every 6 (cell size is 1x1 pixel):

JosephusDrawing04.png

These drawings have several interesting properties:

  • If we divided the drawing in horizontal lines, the first one has n green squares and 0 black squares, the second one has n - 1 green squares and 1 black square, ..., the last one has 0 green squares and n black squares, but these squares are not necessarily contiguous.
  • Conversely, if we divided the drawing in vertical lines we see a similar pattern, but the lines are not ordered. However, their colors are always contiguous (a first green part, and then a black one).
  • The drawing always contains the same number of green and black squares, ½ n(n+1) of each color.
  • The drawing is highly ordered at top, gradually changing to be highly disordered at bottom. It resembles a Escher drawing that slightly changes from one scene to another.