The Josephus Problem Generalized in J

Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 33

Programs for the generalized Josephus problem and variants are presented using J.

Introduction¶

The Josephus problem is a classic mathematical problem which has been portrayed in various guises and has been programmed in various languages (see [1]), typically for an assignment in computer science. It supposedly originated in the first century when 41 trapped rebels stood in a circle and, rather than be captured, sacrificed every third person remaining. Flavius Josephus and a friend apparently were the two survivors [2]. The question is: where did they stand (indexed from the start position)?

The problem invites generalization in two variables: N, the number of people to start with; and K, the interval for killing. Simulations can be programmed easily; for instance, from [3]:

   j =: }: @ |.

   js =: j ^: (1: + #@] - [)

For example, the original case above:

   3 js i.41
15 30                         NB. Survivors

K js i.N works for any integer N when K=2 but not for N<K-1 when K>2; therefore, K&js\ i.N yields a pattern of results only for K=2. Degenerate case 1 js i.N is empty (correctly) and 0 js i.N is empty (but should be i.N). When K<0, the Josephus problem can be interpreted as killing in the opposite direction, which can be mapped into positive K cases: (|K) js (-K<0)|.i.N**K .

Accordingly, all programs here are defined for K>0 and with N>0 in mind, although most will work for any integer N, where:

K js i.-N is N - >:K js i.N .

The following simulation program accommodates any positive integers K and N (including degenerate cases), and uses input indices for convenience:

   JS =: j ^: (<: #) ^:_ i.

   3 JS 41                    NB. Kill every 3rd of 41
15 30                         NB. Survivors (origin 0)

K JS >:i.N simulations produce results generally useful for analyzing patterns.

Analytic solutions, however, are rare. A nice closed form solution for K=2 exists: represent N in binary, rotate the first digit onto the end, and decode the binary representation. The following function (from [4] and derived in [2]) accomplishes this:

   Josephus =: 1&|. &. #:

For example:

   Josephus 41                NB. Kill every 2nd of 41
19                            NB. Survivor (Origin 1)

An alternative is:

   Josephus =: (- -.) &. #:

Unfortunately, neither lends an obvious generalization for K>2. Instead, recurrence relations have been proffered for K=3 and for K>1 in [2 pages 80-81], as well as for K=2 in [5 page 76] and [3 page 11]. Other non-recursive solutions, such as in [3 page 12] for K=2, apparently haven’t been generalized.

The General Josephus Problem¶

The generalized Josephus problem is restated here as follows:

For N people in a circle, if every Kth remaining person is successively killed, what were the original positions of the K-1 survivors?

Here is a simple recursive program to solve this problem:

   k =: [
   n =: ]
   J =: (n | k + (J <:)) ` (i.@n) @. >

Examples:

   2 J 41
18                            NB. Origin 0

   3 J 41
15 30

   4 J 41
36 10 4

Results of K J"0 >:i.N replicate (albeit inefficiently) K JS"0 >:i.N simulations.

General Josephus Problem Variants¶

A common variant of the General Josephus problem continues the killing until no one remains and reports all killed in order, as in [6]. The following simulation program does this recursively:

   JO =: ({:@|. , k JO }:@|.) ` n @. (#@n <: 1:)

For example:

   3 JO i.41                  NB. Order of killing
2 5 8 11 14 17 20 23 26 29 32 35 38 0 4 9 13 18 22 27 31
   36 40 6 12 19 25 33 39 7 16 28 37 10 24 1 21 3 34 15 30

Or, to report when each person was killed, use the inverse permutation:

   /: 3 JO i.41               NB. When each killed
13 35 0 37 14 1 23 29 2 15 33 3 24 16 4 39 30 5 17 25 6 36
   18 7 34 26 8 19 31 9 40 20 10 27 38 11 21 32 12 28 22

A simpler variant of the General Josephus problem reports only the last survivor, as in [2]. This can be accomplished easily using the previous program. For example:

   {: 3 JO i.41
30

Other Variants¶

Now consider some other variants of the General Josephus problem. First:

For N people in a circle, if the first of every K remaining people is successively killed, what were the original positions of the K-1 survivors?

A simulation program for this problem is:

   j1 =: }. , }.@{.

   JS1 =: j1 ^: (<: #) ^:_ i.

Examples:

   2 JS1 41
17

   3 JS1 41
13 28

   4 JS1 41
33 7 11

Comparing results of K JS1"0 >:i.N with K J"0 >:i.N reveals that JS1 is >:@(J <:) for N>K-1 or i.@(<: <:)~ , >:@(J <:) in general.

Next, a complementary variant (for K>1):

For N people in a circle, if all but the first of every K remaining people are successively killed, what was the original position of the last survivor?

A simulation program for this is JS_1 =: j_1 ^: (#@] > 1:) ^:_ i. where j_1 =: }.,{.@].

Better yet, here is a closed form solution to this problem:

   k =: [
   n =: ]
   J_1 =: mod * (k (* - power) n%mod) % <:@k

   power =: k ^ >:@<.@^.

   mod =: >:@(|&<:)

Examples:

   2 J_1 41
18

   3 J_1 41
21

   4 J_1 41
12

Finally, another related variant:

For N people in a circle, if all but the Kth remaining person are successively killed, what was the original position of the last survivor?

Readers are welcome to help solve this problem and to prove the correctness of the programs given here.

References¶

1. Problem Solving by Programming: Solutions to The Josephus Problem (Revisited), Peelle & Lipp, Journal of Computer Science Education, Vol. 12, No. 1, Fall 1997
2. Concrete Mathematics (2nd edition), Graham, Knuth, & Patashnik, Addison-Wesley, Reading, MA 1994, pages 8–16, 79–81
3. Concrete Math Companion, Kenneth Iverson, Iverson Software Inc., Toronto 1996, pages 10–12
4. At Work and Play in the Fields of J, Eugene McDonnell, Iverson Software, Inc., Toronto 1993, page 16
5. Trains, Agendas, and Gerunds, Hui & Iverson, Proceedings of APL94, Vol. 25, No. 1, ACM, New York, pages 74–77
6. Implementing Discrete Mathematics, Steven Skiena, Addison-Wesley, Redwood City, CA 1990