33. Josephus Problem
1∘⌽⍢⊤
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.
[99]
| |
The phrase J=.1&|.&.#: in J translated into APL is J←1∘⌽⍢⊤ .
It derives by observing that:
⊢ y← 2*?10⍴10
2 128 16 32 4 1 64 64 512 8
J¨ y
1 1 1 1 1 1 1 1 1 1
⊢ y← 1+?10⍴1000
520 831 35 54 530 672 8 384 67 418
(J¨ 1+y) - J¨ 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:
1+5 10⍴⍳×/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¨ 1+5 10⍴⍳×/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 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 (2∘⊥⍣¯1),
rotate by one (1∘⌽),
and invert by computing the binary value (2∘⊥).
As a matter of historical interest, binary representation and binary value
(denoted by the monads ⊤ and ⊥) were once defined in APL
[100],
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).
Appeared in J in
[101].
|