# Essays/Josephus Problem

Being involved in the development of a programming language has its rewards, none more pleasant than receiving gems like the following (EEM is Eugene E. McDonnell):

No. 6122659 filed 2.13.00 Sun 5 Apr 1992 From EEM To KEI RHUI Subj Josephus Problem With n people numbered 1 to n in a circle, every second one is eliminated until only one survives. For example, for n=10, the elimination order is 2 4 6 8 10 3 7 1 9, so 5 survives. The problem: Determine the survivor's number J(n). J=.1&|.&.#: Try J"0 i.50 for a nice pattern to emerge. See also Graham et al, Concrete Mathematics, Section 1.3.

`J `can be derived by observing that:

] y=.2^?10$10 2 128 16 32 4 1 64 64 512 8 J"0 y 1 1 1 1 1 1 1 1 1 1 ] y=.>:?10$1000 520 831 35 54 530 672 8 384 67 418 (J"0 >:y) - J"0 y 2 2 2 2 2 2 2 2 2 2

That is,` J 2^y `is` 1` ,` ` and` (J 1+y)-J y `is` 2 `if` 1+y `is not a power of 2.
As McDonnell asserts, the pattern is made evident by applying` J `to the first few integers:

>: i.5 10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 J"0 >:i.5 10 1 1 3 1 3 5 7 1 3 5 7 9 11 13 15 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37

The statement of` J `in J is interesting in its own right.
` 1&|.&.#: ` is in the form` f&.g` ,` `defined as follows:

` f &.g y ` ` g^:_1 f g y`

` 1&|.&.#: y ` ` #. 1&|. #: y`

That is, convert to the binary representation (`#:`), rotate by one (`1&|.`), and invert by computing the binary value (`#.`).

As a matter of historical interest, binary representation and binary value (denoted by the monads ⊤ and ⊥) were once defined in APL (see Falkoff, Iverson, and Sussenguth [1964]), but were later removed due to space limitations. Such draconian measures are understandable: at the time, APL was running on a S/360 Model 50 with 256 Kbytes of main storage (nevertheless supporting 24 users simultaneously with sub-second response).

**References**

Graham, R.L., D.E. Knuth, and O. Patashnik, *Concrete Mathematics*, Addison-Wesley, 1989, Section 1.3.

Falkoff, A.D., K.E. Iverson, and E.H. Sussenguth, *A Formal Description of System/360*, IBM Systems Journal, Volume 3, Number 3, 1964, Table 1, page 200-201.

Contributed by Roger Hui. Substantially the same text previously appeared in Vector, Volume 9, Number 2, October 1992.