Doc/Articles/Play184
At Play With J ... Table of Contents ... Previous Chapter ... Next Chapter
30. Second Order Josephus
. By Eugene McDonnell. First published in Vector, 18, 4, (April 2002), 132-138.
Every once in a blue moon this column is relatively easy to write. This one almost writes itself. Just a short while ago I received an intriguing message. It forms the bulk of this column. I've just had to change a word here and there and adjust typography as needed. Here's how the message opens:
From bantchev@math.bas.bg Thu Jan 17 18:07:53 2002
Date: Fri, 30 Nov 2001 18:32:13 -0800 (PST)
From: Boyko Bantchev <bantchev@math.bas.bg>
To: forum@jsoftware.com
Subject: Second-order Josephus
In a recent posting Eugene McDonnell defined the verb S that gives the survivor number for the Josephus problem (also in Vector 9/2 (1992)):
S=. 1&|.&.#:
Now suppose that, for n persons, S(n) is not the survivor number, but the one to be eliminated ; i.e., every second person in a circle is marked until only one remains -- and that one is eliminated.
This leads to a "second-order survival problem"; having eliminated S(n), start again from the beginning with the remaining n-1 people, eliminate the one whose ordinal number in the new sequence is S(n-1), then do the same with S(n-2) and so forth until only one is left. What is the number S2(n) of the second-order survivor?
I must confess that my first reaction was somewhat guarded. I wasn't at all sure that this problem would lead to as much in the way of theory as the original Josephus did. For example, the book Concrete Mathematics, by Graham, Knuth, and Patashnik, devotes a full nine pages to Josephus, and gives half a dozen Josephus problems, in section 1.3. However, my mind was open, so I plowed on. Bantchev's message continues:
The verb
E=: ((<:@[{.]),}.)~S@#
eliminates the S#y -th member from any list y, so, if:
n=: 9
and
] y=: 1+i.n
1 2 3 4 5 6 7 8 9
E y
1 2 4 5 6 7 8 9 NB. since 3=S 9
E^:2 y
2 4 5 6 7 8 9 NB. since 1=S 8
E^:3 y
2 4 5 6 7 8 NB. since 7=S 7
E^:4 y
2 4 5 6 8 NB. since 5=S 6
E^:5 y
2 4 6 8 NB. since 3=S 5
E^:6 y
4 6 8 NB. since 1=S 4
E^:7 y
4 6 NB. since 3=S 3
E^:8 y
6 NB. since 1=S 2
Therefore, 6 survives ( 6=S2(9) ). In general, we can set
S2=: E^:(<:@#)@(>:@i.)
but, in fact, it can be shown that, for any n > 1, S2(n) is >: k+2^<:m when k<2^<:m , and 2^m otherwise, where:
m =: <.2^.n ( i.e. (n>:2^m) *. n<2^>:m )
and
k =: n-2^m. So, S2 can be defined without resorting to E or S:
S2 =: (>:@(1&,@({.+.}.)@}.&.#:))"0
and we can check the definition:
S2 2+i.30
2 2 3 4 4 4 5 6 7 8 8 8 8 8 9 10 11 12 13 14 15 16 16 16 16 16 16 16 16 16
To my regret S2 is, though clearly inspired by the definition of S, three times longer than S is, and not at all that elegant. But I did get some fun while writing it, hence my posting it to you.
/Boyko
I studied this message for a while and was confused. Mr. Bantchev gives a formula for S2 which seemed completely different from the immediately preceding formulas. I couldn't reconcile: when k<2 ^ <: m, S2(n) is:
>: k + 2 ^ <: m
otherwise, 2 ^ m
m =: <. 2 ^. n (A) k =: n - 2 ^ m
with:
S2=: (>: @ (1 & , @ ( {. +. }. ) @ }. &. #: ) ) " 0
The leap was too great. I decided to go step by step until I had a better grasp of what was going on. I wrote this function, which follows Boyko's analysis faithfully:
Boyko =: monad define n =. y. m =. <. 2 ^. n k =. n - 2 ^ m if. k < 2 ^ <: m do. >: k + 2 ^ <: m else. 2 ^ m end. )
The argument to Boyko is an integer > 1. It yields the 2d-order Josephus survivor number of that integer:
Boyko"0 [ 2+i.30 2 2 3 4 4 4 5 6 7 8 8 8 8 8 9 10 11 12 13 14 15 16 16 16 16 16 16 16 16 16 (B)
This agrees with the result of S2 in his message. The next step was to take his S2 apart, piece by piece. I'll repeat S2 here, so you can follow the steps:
S2=: (>: @ (1 & , @ ( {. +. }. ) @ }. &. #: ) ) " 0
Taking 19 as argument, convert it to binary:
#:19 1 0 0 1 1
Behead this:
}.#:19 0 0 1 1
"Or" the head with the behead:
({.+.}.)}.#:19
0 1 1
Prefix a 1:
1,({.+.}.)}.#:19
1 0 1 1
Find its base-2 value:
#.1,({.+.}.)}.#:19
11
Add 1:
>:#.1,({.+.}.)}.#:19
12
This validates, but doesn't clarify, how S2 was put together. Since we know that Mr. Bantchev was trying to arrive at a solution that used the binary representations of numbers, I suspected that the answer might be found by looking at the binary values of argument and result side by side:
q=:2+i.20 (,.q);(#:q);(#:w);(,.w =: Boyko"0 q) +--+---------+-------+--+ | 2|0 0 0 1 0|0 0 1 0| 2| | 3|0 0 0 1 1|0 0 1 0| 2| | 4|0 0 1 0 0|0 0 1 1| 3| | 5|0 0 1 0 1|0 1 0 0| 4| | 6|0 0 1 1 0|0 1 0 0| 4| | 7|0 0 1 1 1|0 1 0 0| 4| | 8|0 1 0 0 0|0 1 0 1| 5| | 9|0 1 0 0 1|0 1 1 0| 6| |10|0 1 0 1 0|0 1 1 1| 7| |11|0 1 0 1 1|1 0 0 0| 8| |12|0 1 1 0 0|1 0 0 0| 8| |13|0 1 1 0 1|1 0 0 0| 8| |14|0 1 1 1 0|1 0 0 0| 8| |15|0 1 1 1 1|1 0 0 0| 8| |16|1 0 0 0 0|1 0 0 1| 9| |17|1 0 0 0 1|1 0 1 0|10| |18|1 0 0 1 0|1 0 1 1|11| |19|1 0 0 1 1|1 1 0 0|12| |20|1 0 1 0 0|1 1 0 1|13| |21|1 0 1 0 1|1 1 1 0|14| +--+---------+-------+--+
It takes a bit of study, but it should be possible eventually to arrive at the S2 solution. Notice that the leading bit plays no role. The significant bit is the second. When this is 1, the result will be a power of 2, because the "or" of the second bit with the trailing bits will produce all 1s, prefixing a 1 keeps them all ones, converting this to integer will produce a result one less than a power of two, and adding one to this will yield a power of two. When the second bit is 0, the trailing bits are unaltered. When 1 is prefixed, the result will be a power of two only when the trailing bits are all 1, as in the case of 11. The binary form of 11 is 1 0 1 1; beheading gives 0 1 1; "or"ing 0 with 1 1 gives 1 1; prefixing 1 gives 1 1 1; converting to integer gives 7; adding one gives 8, a power of two.
I'm guessing that Mr. Bantchev followed a process much like the one I've described just above: finding the values with his algebraic analysis, converting these to binary, and comparing them with the binary form of the arguments. This is now enshrined in Sloane's On-Line Encyclopedia of Integer Sequences as sequence A066997.
I thought I had found an interesting property of (B). I noted the indices (in 2-origin) of the first appearance of a power of two were at indices 2, 5, 11, 23. I checked in the Online Encyclopedia of Integer Sequences and found that it corresponded to sequence A055010. The entry notes that these numbers, written in binary, are of the form a(n) is 10111111. Furthermore, it gave the following formula for a(n):
a(n) = (3*2^n)-1
I sent a message to Henry Bottomley, the author of this entry, and he in his reply alerted me to the existence of sequence A006165, which is:
1 1 2 2 3 4 4 4 5 6 7 8 8 8 8 8 9 10 11 12 13 14 15 16 16 16 16 16 16 ...
This should be familiar, as it is the S2 sequence, with two leading 1s. I kicked myself for not having found this on my own, and began to appreciate that Mr. Bantchev might be on to something not completely trivial. The entry for series A006165, gives two recursive formulas, one for odd n, and the other for even:
a((2*n)+1) = a(n+1)+a(n) (A) a(2*n) = 2*a(n) (B)
By a bit of finagling it's possible to combine these two into one. The ceiling and floor of (2*n)+1 are (n+1) and (n), as in (A) above. The ceiling and floor of 2*n are both n, as in (B) above. This makes it possible, for whatever integer, to get the result by the same formula, which takes the sum of the ceiling and floor of half the number. The explicit function A below takes as argument the number of consecutive survivor numbers desired, and yields that many. For an argument of 0 it yields an empty list, and for an argument of 1 it yields a list whose item is 1.
A =: monad define
if.
y. < 2
do.
y. # 1
else.
a =. 1 1
while.
y. > # a
do.
b =. ( <. , >. ) -: <: # a
a =. a , + / b { a
end.
end.
)
This duplicates A006165 faithfully. It differs from Bantchev's series in using offset 1. I found a much faster way to generate the sequence. It forms two lists, first just the 1-origin integers, then the extra powers of two needed:
(>:i.+/2^i.y.) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ;(#each+:)2^i.y. 2 4 4 8 8 8 8 16 16 16 16 16 16 16 16
Joins these, and sorts them:
1 2 2 3 4 4 4 5 6 7 8 8 8 8 8 9 10 11 12 13 14 15 16 16 16 16 16 16 16 16
Here is the high-speed Josephus 2 function:
hsJ2=: 13 : '/:~(>:i.+/2^i.y.),;(#each+:)2^i.y.'
Its argument is the number of powers of 2 to use in generating the lists, and the result is a list as long as twice the sum of those powers of 2:
2^i.4 1 2 4 8 +/2^i.4 15 +:+/2^i.4 30 hsJ2 4 1 2 2 3 4 4 4 5 6 7 8 8 8 8 8 9 10 11 12 13 14 15 16 16 16 16 16 16 16 16 #hsJ2 4 30