Differences between revisions 7 and 8
 ⇤ ← Revision 7 as of 2007-09-05 21:58:04 → Size: 2851 Editor: RogerHui Comment: ← Revision 8 as of 2008-12-08 10:45:40 → ⇥ Size: 2855 Editor: anonymous Comment: converted to 1.6 markup Deletions are marked like this. Additions are marked like this. Line 61: Line 61: ` f &.g y ` [[latex(\$\leftrightarrow\$)]] ` g^:_1 f g y` [[BR]]` 1&|.&.#: y ` [[latex(\$\leftrightarrow\$)]] ` #. 1&|. #: y` [[BR]] ` f &.g y ` <> ` g^:_1 f g y` <
>` 1&|.&.#: y ` <> ` #. 1&|. #: y` <
> Line 68: Line 68: [http://www.research.ibm.com/journal/sj/032/falkoff.pdf Falkoff, Iverson, and Sussenguth [1964]]), [[http://www.research.ibm.com/journal/sj/032/falkoff.pdf|Falkoff, Iverson, and Sussenguth [1964]]]), Line 80: Line 80: [[BR]] <
> Line 83: Line 83: Substantially the same text previously appeared in [http://www.vector.org.uk Vector], Substantially the same text previously appeared in [[http://www.vector.org.uk|Vector]],

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.```

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 RogerHui. Substantially the same text previously appeared in Vector, Volume 9, Number 2, October 1992.

Essays/Josephus Problem (last edited 2008-12-08 10:45:40 by anonymous)