Second-order Josephus

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

It was nice to see Eugene McDonnell’s "At Play with J" column in Vector 18:4 on "Second-order Josephus" which relates to previous articles in Vector on the Josephus problem. Hopefully there will be more in the future.

Gene cited Boyko Bantchev who recalled the neat verb to compute the Josephus survivor number:

S =: 1&|.&.#:

The reader should be cautioned that the input and result are in origin 1 while J uses origin 0, and that this verb does not generalize to the original Josephus problem (using a killing interval of three) nor to other intervals.

Bantchev proffered J verbs to solve the Second-order Josephus problem, beginning with a verb to eliminate item S #y from any list y which, if restricted to unique items (as needed here), can be written more succinctly as:

E =: -. <:@S@# { ]

This can be embodied in a master verb using a gerund to find the Second-order survivor number by simulation:

S2a =: E ^: (<: ` Natural)
        Natural =: >:@i.

Interested in producing a sequence of such results directly, Gene offered a "high-speed" verb to compute all but one last item using a power of 2 needed for input. I’ve rewritten it tacitly here to produce the full sequence:

J2t =: Sort @ (Natural@Power , Copy@Power@i.)
        Sort =: /:~
        Natural =: }.@i.@>:
        Power =: 2&^
        Copy =: # +:

The following alternative definition is more efficient without sorting:

J2r =: >:@Copies # Natural@Power
    Copies =: Power@i. In} Power # 0:
        In =: <:@+:@[

An even more efficient definition is:

J2b =: +/\ @ Bits =: 1: , ;@:(Take each)@Power@i.
    Take =: +: {. (# 1:)

This verb runs about 8 times faster than Gene’s hsJ2 in about 30% space for a sample input of 12 (using J4.06a on a Pentium II PC running Windows 95 with 256M).

Gene’s column could have concluded with a verb to solve the Second-order Josephus problem:

S2c =: <: { J2x @ Enuf =: >.@Log =: 2&^.

But, of course, this is redundant. Instead, Bantchev offered a verb S2 using base-2 encoding to solve the problem (except for an input of 1). Here is an alternative inclusive definition:

S2p =: (] <. 1: + (- -:)) <.&.(2&^.)

This definition produces the Second-order Josephus sequence about 6 times faster than Bantchev’s S2 for 2+i.30 and generally runs even faster (but in increasingly more space) for larger inputs. (But who would want to do so much killing?!)