solution to the josephus problem

Josephus Problem

Another version of the problem considers a circle of two groups (say, "A" and "B") of 15 men each (giving a total of 30 men), with every ninth man cast overboard, illustrated above. To save all the members of the "A" group, the men must be placed at positions 1, 2, 3, 4, 10, 11, 13, 14, 15, 17, 20, 21, 25, 28, 29. Written out explicitly, the order is

If instead every tenth man is thrown overboard, the men from the "A" group must be placed in positions 1, 2, 4, 5, 6, 12, 13, 16, 17, 18, 19, 21, 25, 28, 29. Written out explicitly,

which can be constructed using the Latin mnemonic "Rex paphi cum gente bona dat signa serena" (Ball and Coxeter 1987).

(OEIS A032435 ).

(OEIS A032436 ).

Explore with Wolfram|Alpha

More things to try:

• tower of Hanoi
• 30-sided polyhedron
• curl [-y/(x^2+y^2), -x/(x^2+y^2), z]

Referenced on Wolfram|Alpha

Cite this as:.

Weisstein, Eric W. "Josephus Problem." From MathWorld --A Wolfram Web Resource. https://mathworld.wolfram.com/JosephusProblem.html

Subject classifications

• 15 Puzzle Game: Existence Of The Solution
• The Stern-Brocot Tree and Farey Sequences

Josephus Problem ¶

Statement ¶.

We are given the natural numbers $n$ and $k$ . All natural numbers from $1$ to $n$ are written in a circle. First, count the $k$ -th number starting from the first one and delete it. Then $k$ numbers are counted starting from the next one and the $k$ -th one is removed again, and so on. The process stops when one number remains. It is required to find the last number.

This task was set by Flavius Josephus in the 1st century (though in a somewhat narrower formulation: for $k = 2$ ).

This problem can be solved by modeling the procedure. Brute force modeling will work $O(n^{2})$ . Using a Segment Tree , we can improve it to $O(n \log n)$ . We want something better though.

Modeling a $O(n)$ solution ¶

We will try to find a pattern expressing the answer for the problem $J_{n, k}$ through the solution of the previous problems.

Using brute force modeling we can construct a table of values, for example, the following:

And here we can clearly see the following pattern :

Here, 1-indexing makes for a somewhat messy formula; if you instead number the positions from 0, you get a very elegant formula:

So, we found a solution to the problem of Josephus, working in $O(n)$ operations.

Implementation ¶

Simple recursive implementation (in 1-indexing)

Non-recursive form :

This formula can also be found analytically. Again here we assume 0-indexing. After we delete the first number, we have $n-1$ numbers left. When we repeat the procedure, we will start with the number that had originally the index $k \bmod n$ . $J_{n-1, k}$ would be the answer for the remaining circle, if we start counting at $0$ , but because we actually start with $k$ we have $J_{n, k} = (J_{n-1,k} + k) \ \bmod n$ .

Modeling a $O(k \log n)$ solution ¶

For relatively small $k$ we can come up with a better solution than the above recursive solution in $O(n)$ . If $k$ is a lot smaller than $n$ , then we can delete multiple numbers ( $\lfloor \frac{n}{k} \rfloor$ ) in one run without looping over. Afterwards we have $n - \lfloor \frac{n}{k} \rfloor$ numbers left, and we start with the $(\lfloor \frac{n}{k} \rfloor \cdot k)$ -th number. So we have to shift by that many. We can notice that $\lfloor \frac{n}{k} \rfloor \cdot k$ is simply $-n \bmod k$ . And because we removed every $k$ -th number, we have to add the number of numbers that we removed before the result index. Which we can compute by dividing the result index by $k - 1$ .

Also, we need to handle the case when $n$ becomes less than $k$ . In this case, the above optimization would cause an infinite loop.

Implementation (for convenience in 0-indexing):

Let us estimate the complexity of this algorithm. Immediately note that the case $n < k$ is analyzed by the old solution, which will work in this case for $O(k)$ . Now consider the algorithm itself. In fact, after every iteration, instead of $n$ numbers, we are left with $n \left( 1 - \frac{1}{k} \right)$ numbers, so the total number of iterations $x$ of the algorithm can be found roughly from the following equation:

on taking logarithm on both sides, we obtain:

using the decomposition of the logarithm into Taylor series, we obtain an approximate estimate:

Thus, the complexity of the algorithm is actually $O (k \log n)$ .

Analytical solution for $k = 2$ ¶

In this particular case (in which this task was set by Josephus Flavius) the problem is solved much easier.

In the case of even $n$ we get that all even numbers will be crossed out, and then there will be a problem remaining for $\frac{n}{2}$ , then the answer for $n$ will be obtained from the answer for $\frac{n}{2}$ by multiplying by two and subtracting one (by shifting positions):

Similarly, in the case of an odd $n$ , all even numbers will be crossed out, then the first number, and the problem for $\frac{n-1}{2}$ will remain, and taking into account the shift of positions, we obtain the second formula:

We can use this recurrent dependency directly in our implementation. This pattern can be translated into another form: $J_{n, 2}$ represents a sequence of all odd numbers, "restarting" from one whenever $n$ turns out to be a power of two. This can be written as a single formula:

Analytical solution for $k > 2$ ¶

Despite the simple form of the problem and a large number of articles on this and related problems, a simple analytical representation of the solution of Josephus' problem has not yet been found. For small $k$ , some formulas are derived, but apparently they are all difficult to apply in practice (for example, see Halbeisen, Hungerbuhler "The Josephus Problem" and Odlyzko, Wilf "Functional iteration and the Josephus problem").

• singamandeep (63.09%)
• jakobkogler (17.45%)
• AbhijeetKrishnan (12.75%)
• adamant-pwn (4.7%)
• algmyr (1.34%)
• diksown (0.67%)