Korean J. Math. 26 (2018), No. 1, pp.

1–7
[Link]

SERIAL EXECUTION JOSEPHUS PROBLEM

Jang-Woo Park∗ and Ricardo Teixeira

Abstract. In this paper, we will study a generalized version of

Josephus where a serial execution occurs at each iteration and give
a non-recursive formula for the initial positions of survivors.

1. Introduction

Josephus problem is named after Flavius Josephus, a Jewish historian

in the first century [4]. The problem statement is as follows: There are
n people, numbered from 0 to n − 1 in a circle. In the first iteration,
the person 0 is skipped and the person 1 is executed. In the second
iteration, the person 2 is skipped and the person 3 is executed. Then
the iteration is repeated until there is only one person remaining. A
question that may arise is where to stand to be the last survivor. The
Josephus problem is to find the initial position of the survivor in the
scenario described above. Popular generalization of the problem is to
allow skipping more than one person followed by executing one person.
This version has been extensively studied in [2], [3], [5], [6], [8], [11],
and [12]. In [7], Ruskey and Williams introduced an interesting variant
of the problem in which each person has multiple lives, hence the name
is a “feline Josephus problem”. Sharma et al [9] studied a version where
Received October 9, 2017. Revised December 17, 2017. Accepted January 12,
2018.
2010 Mathematics Subject Classification: 68R01, 97N70.
Key words and phrases: Josephus problem, discrete mathematics, function
iterations.
∗ Corresponding author.
c The Kangwon-Kyungki Mathematical Society, 2018.
This is an Open Access article distributed under the terms of the Creative com-
mons Attribution Non-Commercial License ([Link]
-nc/3.0/) which permits unrestricted non-commercial use, distribution and reproduc-
tion in any medium, provided the original work is properly cited.
2 Jang-Woo Park and Ricardo Teixeira

the number of persons that are skipped in each iteration changes. The
original Josephus problem is also a main idea behind a famous magic
trick [1] and [10] provided the mathematical generalization of the magic
trick.

2. Generalized Josephus Problem

In this section, we generalize Josephus Problem. Suppose there are n

people, numbered from 0 to n − 1 in a circle. Starting from the person
0, the following iteration is applied: skip s people and execute k people
after. The iteration is repeated until there are at most k people left. We
exclude the case where there is no survivor. Without loss of generality,
we assume that n, k, and s are positive integers and n ≥ k.
Proposition 2.1. Let I be the total number of iterations and P the
number of survivors at the end. Then
( 
n
if n 6≡ 0 (mod k)
I =  nk 
k
− 1 if n ≡ 0 (mod k).
and (
n mod k if n 6≡ 0 (mod k)
P =
k if n ≡ 0 (mod k).
Proof. It is obvious since after each iteration, the number of people
will decrease by k and we repeat until the number of people is less than
or equal to k.
Definition 2.2. Suppose that we have a situation described above.
A generalized Josephus problem J(n, s, k; i) is to find the initial position
of the ith survivor after I iterations.
With this definition, the original Josephus problem can be viewed
as J(n, 1, 1; 1). We are interested in finding the initial positions of all
survivors without performing the procedure. To understand the problem
better, we view skipping s people as shifting the starting point of the
positions of people in the sequence and executing k people as deleting
them from the sequence. For example, in the beginning of J(10, 2, 3; 1),
we have
0 1 2 3 4 5 6 7 8 9
 Serial execution Josephus problem 3

Then, after skipping 2 people, we have

2 3 4 5 6 7 8 9 0 1
Then, we execute 3 people and we have
5 6 7 8 9 0 1
After another iteration is applied,
0 1 5 6
Then, after the final iteration,
1
Thus, 1 is the survivor. To be consistent with modulo operation,
the positions of people start at 0. As we see, the starting point of
the positions changes after each iteration. The starting point in the
beginning is 0 and the position of 1 is 1. After the first iteration,
the starting point is 5 and the position of 1 is 6. After the second
iteration, 0 is the starting point and the position of 1 is 1. Then,
after the final iteration, the position of 1 is 0. So, it is easy to see that,
in J(n, s, k; i), the position of the ith survivor at the end is simply i − 1.
To find the explicit formulas, we will take a backward approach.
Definition 2.3. For 0 ≤ j ≤ I, Si (j) denotes the position of the
ith survivor and N (j) represents the number of people at the (I − j)th
iteration.
Note that the position of the ith survivor at the end is Si (0) = i−1 for
1 ≤ i ≤ P and the number of people at the end is N (0) = P . Using this
notation, we can have a following recurrence relation: For 1 ≤ i ≤ P
and 0 ≤ j ≤ I − 1,
N (j + 1) = N (j) + k
Si (j + 1) = Si (j) + (k + s) (mod N (j + 1))
This recurrence relations suggests that while N (j + 1) > Si (j) + (k + s),
Si (j +1) = Si (j)+(k +s) and since Si (·) increases faster than N (·), Si (·)
will eventually catch up N (·) and move to the front of the sequence. To
find out when this would happen, we introduce the following term:
Definition 2.4. The mth crossover of the ith survivor, denoted by
Cri (m), is the number of iterations, j, such that 0 ≤ Si (j) < s for the
mth time.
4 Jang-Woo Park and Ricardo Teixeira

In the rest of the paper, we focus on J(n, 1, k; i) where k consecutive

people are executed in each iteration.
Lemma 2.5. In J(n, 1, k; i), Si (Cri (m)) = 0 for all m.
Proof. When the mth crossover happens, 0 ≤ Si (Cri (m)) < s by the
definition. Since s = 1 in J(n, 1, k : i), Si (Cri (m)) = 0.
Lemma 2.6. In J(n, 1, k; i) with P survivors,
N (Cri (1)) = P + (P − i + 1)k.
Proof. Consider the ith survivor where 1 ≤ i ≤ P . We already know
that Si (0) = i − 1. Then Cri (1) = j where j is the smallest integer
satisfying
N (j) ≤ Si (j − 1) + (k + 1).
Then j = dle such that
P + l · k = (i − 1) + l · (k + 1).
Since l = P − i + 1, which is an integer, j = l, i.e. Cri (1) = (P − i + 1).
Thus, N (Cri (1)) = P + (P − i + 1)k.
Lemma 2.7. For all positive integer m,
N (Cri (m)) = (P + (P − i + 1)k)(k + 1)m−1 .
Proof. We will prove this using the mathematical induction. Lemma 2.6
proves the base case. Assume that for any m ≥ 1, N (Cri (m)) =
(P + (P − i + 1)k)(k + 1)m−1 . Then Cri (m + 1) = Cri (m) + j where j
is the smallest positive integer satisfying
N (Cri (m)) + k · j ≤ Si (Cri (m)) + (k + 1) · j.
Since Si (Cri (m)) = 0 by Lemma 2.5, Cri (m + 1) = Cri (m) + dle where
l is the solution of the following equation:
(P + (P − i + 1)k)(k + 1)m−1 + k · l = (k + 1) · l.
Thus, by solving the equation, we can find the number of iterations
required to reach from Cri (m) to Cri (m + 1). In this case, the value of
l is an integer and
l = (P + (P − i + 1)k)(k + 1)m−1 .
 Serial execution Josephus problem 5

So,
N (Cri (m + 1))
= N (Cri (m)) + l · k
= (P + (P − i + 1)k)(k + 1)m−1 + (P + (P − i + 1)k)(k + 1)m−1 · k
= (P + (P − i + 1)k)(k + 1)m−1 (1 + k)
= (P + (P − i + 1)k)(k + 1)m .
This completes the proof.
Theorem 2.8. In J(n, 1, k; i) with P survivors, for 1 ≤ i ≤ P , n can
be decomposed as
n = (P + (P − i + 1)k) · (k + 1)α + β · k
where α and β are nonnegative integers and α is the highest such power.
Consequently, the initial position of the ith survivor, Si (I), is
Si (I) = β · (k + 1).
Proof. For 1 ≤ i ≤ P , suppose there are α crossovers. Then
n = N (Cri (α)) + β · k
for some nonnegative integer β. So, by Lemma 2.7,
n = (P + (P − i + 1)k) · (k + 1)α + β · k.
Now consider the initial position of the ith survivor. By Lemma 2.6 and
Lemma 2.7, when N (I − β) = (P + (P − i + 1)k) · (k + 1)α , the αth
crossover occurs. This implies
Si (I − β) = 0.
So, by applying β iterations,
Si (I) = β · (k + 1).

Here is an example.

 207Example
 2.9. Consider J(207, 1, 4; i). Since 207 mod 4 = 3 and
4
= 51, P = 3 and I = 51.
6 Jang-Woo Park and Ricardo Teixeira

• For J(207, 1, 4; 1), (P + (P − i + 1) · k) = 15. So

207 = 15 · 51 + 132 = 15 · 51 + 33 · 4.
Thus, the initial position, S1 (51) = 33 · 5 = 165, i.e. So the 166th
person will be the first survivor.
• For J(207, 1, 4; 2), (P + (P − i + 1) · k) = 11.
207 = 11 · 51 + 152 = 15 · 51 + 38 · 4.
Thus, the initial position, S2 (51) = 38 · 5 = 190. Thus, the 191st
person will be the second survivor.
• For J(207, 1, 4; 3), (P + (P − i + 1) · k) = 7. So
207 = 7 · 52 + 32 = 7 · 52 + 8 · 4.
So, the initial position, S3 (51) = 8 · 5 = 40. Thus, the 41st person
will be the third survivor.

3. Conclusion

In this paper, we provided the explicit formulas of the positions of

the survivors in J(n, 1, k; i) for any positive integer k. The general case
of the Josephus problem, J(n, s, k; i), is still open. We will investigate
other cases to which the same approach can be applied. We will continue
studying the behavior of the crossovers for general case as we have seen
that their behaviors were closely related to the explicit formulas. It is
also very interesting to consider the serial execution case with multiple
lives similar to the case studied in [7].

References
[1] W. Aragon, A Book in English (2011).
[2] L. Halbeisen and N. Hungerbühler, The Josephus Problem, Journal de Thèorie
des Nombres de Bordeaux, 9 (1997), 303–318.
[3] F. Jakóbczyk, On the Generalized Josephus Problem, Glasgow Mathematical
Journal 14 (1973), 168–173.
[4] Titus Flavius Josephus, The Jewish War. 75. ISBN 0-14-044420-3.
[5] A.M. Odlyzko and H.S. Wilf, Functional iteration and the Josephus problem,
Glasgow Mathematical Journal 33 (2) (1991), 235–240.
[6] W.J. Robinson, The Josephus Problem, The Mathematical Gazette 44 (347)
(1960), 47–52.
[7] F. Ruskey and A. Williams, The Feline Josephus Problem, Theory of Computing
Systems 50 (1) (2012), 20–34.
 Serial execution Josephus problem 7

[8] A. Shams-Baragh, Formulation of the Extended Josephus Problem, National

Computer Conference (December 2002).
[9] S. Sharma, R. Tripathi, S. Bagai, R. Saini, and N. Sharma, Extension of the
Josephus Problem with Varying Elimination Steps, DU Journal of Undergradu-
ate Research and Innovation 1 (3) (2015), 211–218.
[10] R. Teixeira and J.W. Park, Mathematical Explanation and Generalization of
Penn and Teller’s Love Ritual Magic Trick, Journal of Magic Research 8 (2017),
21–32.
[11] N. Thèriault, Generalizations of the Josephus Problem, Util. Math. 58 (2000),
161–173.
[12] D. Woodhouse, The Extended Josephus Problem, Rev. Mat. Hisp. Amer. (Ser.
4) 31 (1973), 207–218.

Jang-Woo Park
School of Arts and Sciences
University of Houston-Victoria
Victoria, TX 77901, USA
E-mail : parkj1@[Link]
Ricardo Teixeira
School of Arts and Sciences
University of Houston-Victoria
Victoria, TX 77901, USA
E-mail : teixeirar@[Link]