A Tutorial in J Programming: The Second-Order Josephus Sequence
Vector 19:3, page 46
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 46
Abstract¶
An interesting sequence of non-decreasing positive integers serves as a focus for a tutorial on J programming. Six different approaches and accompanying algorithms are described, each with an overview of its purpose, relevant references, J code, syntactic structure and names of symbols, detailed explanation of the algorithm, examples of execution, and comments. The algorithms are compared for efficiency in speed and space. Concluding insights and programming challenges include a simple strategy for solving the Second-order Josephus problem.
Introduction¶
Consider the sequence
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 16 … .
This sequence appears (with another leading 1) in [1] and is interesting because it lists answers to the "Second-order Josephus" problem (see below), recently posed by Boyko Bantchev in [2]. Related programs have been written by him and Eugene McDonnell in [2] and by Howard Peelle in [3].
The sequence is also instructive as a programming problem which invites different approaches and algorithms. Here we will present and compare several different J programs for producing this sequence – replete with detailed explanations of intermediate programming techniques. (For an introduction to programming in J, see [0] or appropriate books on the Jsoftware website.)
The Second-order Josephus Problem¶
The "Second-order Josephus" problem is derived from the basic "Josephus" problem ([4],[5],[6]) which is to determine the index of the survivor among N people in a circle where every second person is successively killed. For example, for N=9, numbers 2,4,6,8 (in index origin 1) are killed, then 1,5,9, then 7, leaving number 3 as the survivor.
The Second-order Josephus problem is to determine the index of the last survivor when those identified as survivors of the Josephus problem are successively killed. For example, for N=9, number 3 is killed, then (for N=8) 1 is killed, then similarly (for decreasing N) 9, 7, 5, 2, 8, 4, leaving number 6 as the last survivor.
The reader may wish to pause and write a program to solve this problem before reading on.
Utility Programs¶
To begin, here are some utility programs which will be needed.
Natural numbers¶
Purpose: Generate consecutive integers from 1 to input integer.
Symbols/Syntax: Natural is (Behead Atop Integers) Atop Increment. Note that the Atop conjunction (@) applies the entire verb train on its left after the verb immediately on its right.
Explanation: For input integer y, first add 1. Then generate a list of integers 0 to y. Finally, drop the first item and return the list of integers 1 to y.
Example: >:9 is 10. Then i.10 is 0 1 2 3 4 5 6 7 8 9. Finally, }.0 1 2 3 4 5 6 7 8 9 is 1 2 3 4 5 6 7 8 9. Using the program:
Comment: A shorter definition is Natural=:>:@i. but it is slightly less efficient for large inputs.
Sort¶
Purpose: Sort a list of numbers into ascending order.
Symbols/Syntax: Sort SortUp Reflex. Note that adverb Reflex (syntax u~) applies to a dyadic verb u with input y on both sides, that is, y u y.
Explanation: For an input list y, /:~y is y/:y, which returns the items of y in the order specified by y – that is, the order which would sort y ascendingly.
Example: /:~ 1 2 3 4 5 6 7 2 4 4 8 8 8 8 is 1 2 2 3 4 4 4 5 6 7 8 8 8 8. Using the program:
Comment: An alternative definition is Sort=:]/:] where ] is the input.
Two-Power¶
Purpose: Compute powers of 2.
Symbols/Syntax: Power is 2 With Power. Note that the With conjunction (n&v) uses a noun n on one side (here 2) and a verb v on the other side (here dyadic primitive Power ^) to create a monadic verb.
Explanation: 2 raised to the power of input y.
Example: 2&^ 4 is 16. Using the program:
Comments: Power allows a list input: Power 0 1 2 3 is 1 2 4 8.
An alternative definition is Power =: 2: ^ ] where 2: is the constant verb Two and ] is the input.
Log¶
Purpose: Compute base-2 logarithms.
Symbols/Syntax: Log is 2 With Logarithm. Note that the With conjunction (n&v) uses a noun n on one side (here 2) and a verb v on the other side (here dyadic primitive Logarithm ^.) to create a monadic verb.
Explanation: Base-2 logarithm of input y.
Example: 2&^. 16 is 4. Using the program:
Comment: Log allows a list input: Log 1 2 4 8 is 0 1 2 3.
An alternative definition is Log =: 2: ^. ] where 2: is the constant verb Two and ] is the input.
Each Atom¶
Purpose: Apply a verb (or program) to each atom of input.
Symbols/Syntax: EACH is Rank Zero. Note that EACH is an adverb created from the Rank conjunction (u"n) with the noun 0 on its right. Verb u will be input on the left of EACH.
Explanation: For u EACH y, verb u is applied to each atom of y.
Example: i."0 (1 2 3 4) is list i.1, list i.2, list i.3, list i.4 arranged in a table, with 0 fill elements. Using the program:
Comment: A different definition is needed for boxed nouns. (See next utility program.)
Each Box¶
Purpose: Apply a verb (or program) to each item of input in boxes.
Symbols/Syntax: each is Under Open. Note that each is an adverb created from the Under conjunction (u&.v) with the Open verb (>) on its right. Verb u will be input on the left of each.
Explanation: For u each y, verb u is applied to each item of Open y and then each result is Boxed (the inverse of Open).
Example: i.&.> 1 2 3 4 is boxed list i.1, boxed list i.2, boxed list i.3, boxed list i.4 arranged in a list of boxes. Using the program:
Comment: In the result above there are four items, each containing a list in a box.
J Program for the Josephus Problem¶
Here is a program (verb) in J to compute the survivor number for the Josephus problem using a well-known algorithm ([4],[5]):
Symbols/Syntax: S is (1 With Rotate) Under AntiBase. Note that the Under conjunction (u&.v) executes verb v, then verb u, and finally the inverse of v.
Explanation: Represent integer input y in binary digits. Then rotate one bit from the front to the back. Then return its base-2 value.
Examples: #:9 is 1 0 0 1. Then 1&|. 1 0 0 1 is 0 0 1 1. Finally, #. 0 0 1 1 is 3. Using the program, for 9 people in a circle, the survivor is in position 3:
Comments: The reader should be cautioned that the result is in origin 1 while J uses origin 0. And, unfortunately, this neat verb does not generalize to the original Josephus problem (stated in [4]) using an interval of three nor to other intervals.
Programs for the Second-order Josephus Problem¶
Now, six different approaches and accompanying algorithms will be described for solving the Second-order Josephus problem.
1. Simulation Approach¶
The problem can be solved by simulation – that is, by starting with a list of integer indices and successively eliminating the index of the Josephus survivor (computed by program S above).
In [2] Bantchev provided a verb E=:((<:@[{.]),}.)~S@# to eliminate the (S #y)-th item from any list y. This verb could be rewritten as:
Symbols/Syntax: E is (((Curtail Atop Take) Append Drop) Commute) (S Atop Tally). Note that E is a "hook"(g h) which applies monadic verb h to the input and then dyadic verb g to the input and that result; that is y g h y here. The adverb ~ is used to switch the inputs of g so that S@# becomes the left input and y the right input. Note also that the verb inside the parentheses is a "fork"(f g h) which applies the central verb g to the results of verb f and verb h; that is, (f y) g (h y) here.
Explanation: Remove the last item of the first S@# items taken from list y. Then append it to the list of S@# items dropped from y.
Example: For an input list y=:1 2 3 4 5 6 7 8 9, #y is 9 and S 9 is 3 (as shown above). 3{.y is 1 2 3 and }:1 2 3 is 1 2. And 3}.y is 4 5 6 7 8 9. Appending (}:3{.y),(3}.y) gives the result 1 2 4 5 6 7 8 9. Using the program:
Comment: Note that this verb uses S which uses origin 1 indexing.
Peelle [3] previously offered a more succinct verb to eliminate item S #y:
Symbols/Syntax: E is input Less (((Decrement Atop S) Atop Tally) From Input). Note that E is a hook (g h) where h is a fork (f1 g1 h1), so execution is y -. ((<:S#y) { y).
Explanation: Remove from input list y the item in the (origin 0) position one less than j of the length of y.
Example: For input list y=:1 2 3 4 5 6 7 8 9, #y is 9, then S 9 is 3, and <:3 is 2. Then 2{y is 3. Then 1 2 3 4 5 6 7 8 9 -. 3 is the result, as shown by using the program:
Comment: Input y should be restricted to unique items (as in the example here).
Repeating E simulates the Second-order Josephus problem. For example:
E Natural 9
1 2 4 5 6 7 8 9
E E Natural 9
2 4 5 6 7 8 9
E E E Natural 9
2 4 5 6 7 8
E E E E Natural 9
2 4 5 6 8
E E E E E Natural 9
2 4 6 8
E E E E E E Natural 9
4 6 8
E E E E E E E Natural 9
4 6
E E E E E E E E Natural 9
6
This can be accomplished in one expression:
Symbols/Syntax: (E Power 8) (Natural 9). Note that the Power conjunction (u^:n) here uses verb E on the left and noun 8 on the right. Natural 9 is the input for E^:8. Note that the input could be entered directly, as in E^:8 (1 2 3 4 5 6 7 8 9) or using Right (]) to separate 8 from the input numbers, as in E^:8 ] 1 2 3 4 5 6 7 8 9.
Explanation: E is repeated 8 times on its own result, starting with the natural integers 1 to 9 input. Note that this illustrates how to do iteration in J.
Example: For input y=9, Natural 9 is 1 2 3 4 5 6 7 8 9, and E^:8 Natural 9 is 6 (as shown above).
Comment: This could be embodied in a master program.
Bantchev [2] offered a master verb S2=:E^:(<:@#)@(>:@i.). An alternative definition, using a gerund, is:
Symbols/Syntax: S2a is E Power (Decrement Tie Natural). Note that a gerund is a boxed noun containing verbs. Here, the gerund produced by ` allows the input for ^: to be entered along with the input y for the derived verb E^:<:.
Explanation: Repeat E one less number of times than input y, starting with input integers 1 to y.
Example: For input 9, <:9 is 8 and Natural 9 is 1 2 3 4 5 6 7 8 9. E^:8 (1 3 2 3 4 5 6 7 8 9) is 6 (as shown earlier). Using the program for a list of inputs produces the Second-order Josephus sequence:
Comments: The utility program EACH is required to apply S2a to each item of the input list separately. Ravel (,) is used to display the resulting array of 1-item lists as one list.
2. Sorting Approach¶
The Second-order Josephus sequence can be produced directly – that is, without resorting to simulation – by sorting indices together with copies of powers of 2.
McDonnell [2] offered a "high-speed" verb hsJ2=:13 : '/:~(>:i.+/2^i.y.),;(#each+:)2^i.y.' which generates the sequence without the last item. Here is a revised explicit definition to produce a full sequence:
Symbols/Syntax: J2x is verb Define (SortUp Commute) ((Natural (Two Power input)) Append ((Copy Double) (Two Power (Integers input)))). Note that 13 : indicates a verb is being defined explicitly (using input y.) for conversion to tacit form, and its monadic definition is given in quotes on the right.
Explanation: The input is the power of 2 needed to produce the sequence. Overall, the program sorts into ascending order the result of appending two lists. One list is the Natural integers from 1 to input y. The other list is c copies of double c, where c is a list of powers of two from 1 to 2 raised to one less than input y.
Example: For input 4, i.4 is 0 1 2 3, and 2^0 1 2 3 is 1 2 4 8, and +:1 2 4 8 is 2 4 8 16, and 1 2 4 8 # 2 4 8 16 is p=:2 4 4 8 8 8 8 16 16 16 16 16 16 16 16. Then 2^4 is 16, and Natural 16 is n=:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16. Then n,p is r=:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 2 4 4 8 8 8 8 16 16 16 16 16 16 16 16. Finally /:~r is the result below using the program:
Comment: An explicit definition for a verb can be entered without quotes on successive lines (if needed) using 3 : 0 with a final right parenthesis to close the definition.
Peelle [3] offered an equivalent program using tacit definition:
Symbols/Syntax: J2t is Sort Atop ((Natural Atop Power) Append ((Copy Atop Power) Atop Integers)). Copy is input Copy Double. (See Utility Programs earlier for definitions of Natural, Power and Sort.)
Explanation: Input y is the power of 2 needed to produce the sequence. One list is natural numbers 1 to 2^y. Another list is powers of 2 (2^i.y) copies of doubled powers of 2. Sort the two lists into ascending order.
Examples: For an input of 4, i.4 is 0 1 2 3. Then Power 0 1 2 3 is 1 2 4 8. Then Copy 1 2 4 8 is 1 2 4 8 # 2 4 8 16 which is c=:2 4 4 8 8 8 8 16 16 16 16 16 16 16 16. Then Power 4 is 16. Natural 16 is n=:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16. Then n,c is r=:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 2 4 4 8 8 8 8 16 16 16 16 16 16 16 16. Finally, the result is Sort r as shown in the result below using the program:
Comment: Tacit definition requires specifying verbs without their inputs, which are given upon execution. This is often called "(pure) functional programming" (see [0]).
3. Replication Approach¶
Peelle [3] offered a similar program which replicates indices without sorting:
Symbols/Syntax: J2r is (Increment Atop Copies) Copy (Natural Atop Power). Copies is (Power Atop Integers) (In Amend) (Power Copy Zero). In is (Decrement Atop Double) Atop Left input.
Explanation: Find the number of copies (Copies y) needed and copy each natural number (Natural Power y). Copies produces a list of 0s with powers of 2 substituted in positions of twice the powers of 2.
Example: For input 4, Power 4 is 16 and Natural 16 is 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16. Then (for Copies 4) Power 4 is 16, and 16 # 0 is 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0. Then i.4 is 0 1 2 3 and Power 0 1 2 3 is 1 2 4 8. Then 1 2 4 8 In 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 is 1 3 7 15, so 1 2 4 8 (1 3 7 15}) 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 is 0 1 0 2 0 0 0 4 0 0 0 0 0 0 0 8. Finally, use one plus this list to copy items from Natural 16, as results from the program below:
Comments: A variation is J2r1=:Copies1 # Natural@Power where Copies1=:>:@Power@i. In1} Power # 1: and In1=:<:@+:@<:@[ (which is slightly less efficient until input is very large).
4. Bits Approach¶
Peelle [3] also offered a different program to produce the Second-order Josephus sequence by accumulating sums of ones and zeros:
Symbols/Syntax: J2b is ((Plus Insert) Prefix) Atop Bits. Bits is One Append (((Raze At (Take each)) Atop Power) Atop Integers). Take is Double Take (input Copy One). Note that Bits is defined as a fork (f g h) which is executed as (f y) g (h y). Take is a fork (f1 g1 h1) where h1 is a hook (g2 h2), which is executed together as (f1 y) g1 (y g2 (h2 y)).
Explanation: Accumulate 1s from sub-program Bits which produces a 1 appended to a list of 1s and 0s from boxed lists resulting from (over)taking double the power of 2 copies of 1s and the rest 0s for each integer from 0 to input y minus 1.
Example: For input 4, i.4 is 0 1 2 3, and Power 0 1 2 3 is 1 2 4 8. Take each 1 2 4 8 is boxed list 1 0, boxed list 1 1 0 0, boxed list 1 1 1 1 0 0 0 0, boxed list 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0. Razing (;) the list of these lists is r=:1 0 1 1 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0. Then b=:1,r and cumulative sums +/\b is the result below using the program:
Comments: A variation is: J2b1=:+/\@Bits1=:1:,;@:(Pairs each)@Power@i. where Pairs=:(# 1:),(# 0:).
Another possible variation is: J2b2=:+/\@Bits2=:1:,;@:(Boxes each)@Power@i. where Boxes=:> i.@+: .
5. Base-2 Encoding Approach¶
Bantchev [2] offered an algorithm using base-2 encoding-decoding (for inputs above 1): S2=:(>:@(1&,@({.+.}.)@}.&.#:))"0. An alternative algorithm which accepts an input of 1 is:
S2b =: Shift &. #:
Shift =: -@Second |. One + Half Min Second
Second =: {.@Rotate1=:1&|.
One =: -@# {. 1:
Half =: # {. 0: , 1: , }.@}.
Min =: *. -.
Symbols/Syntax: S2b is Shift Under Antibase2. Note that the conjunction &. executes the verb on its right, then the verb on its left, then the inverse of the right verb (here #. Base2). Shift is (Negate Atop Second) Rotate (One + (Half Min Second)). Note that (Half Min Second) is a fork whose result is used within another fork. Second is Head Atop Rotate1 which is 1 With Rotate. Note that defining Rotate1 in-line obviates parentheses (1&|.). One is (Negate Atop Tally) Take One – a simple fork. Half is Tally Take (Zero Append (One Append (Behead Atop Behead))) – a fork within a fork within a fork. Min is input And Not – a simple hook.
Explanation: Convert the input to a list of binary digits, apply Shift, and then convert back to base-10 value. If the second binary digit is a 1, Shift returns a 1 followed by all zeros (a power of two). Otherwise, if the second bit is 0, Shift returns 1 (with leading zeros) plus the given bits with a leading 0 and a 1 in the second digit (that is, less ‘half’). This is accomplished effectively in Min by ‘anding’ (*.) the given bits with not (-.) the second bit.
Example: For an input 9, #:9 is 1 0 0 1. Shift 1 0 0 1 is 0 1 0 2. And #.0 1 0 2 is 6. Details of Shift 1 0 0 1 are: Second 1 0 0 1 is 0. Half 1 0 0 1 is 0 1 0 1. 0 1 0 1 Min 0 is 0 1 0 1. One 1 0 0 1 is 0 0 0 1. 0 0 0 1 + 0 1 0 1 is 0 1 0 2 (which evaluates correctly in base 2). Using the program for a list of natural numbers produces the sequence:
Comments: EACH is required to execute S2b separately for each natural number input.
An alternative definition which converts bits to base value before finding the minimum is more efficient: S2b1 =: (Min1 Pow1)@#: where Pow1 =: # {. 1: and Min1 =: ] <.&#. Shift1 =: One1 + (-Half1) and One1 =: 1: |. ] and Half1 =: _1: |. ].
6. Log Approach¶
Peelle [3] offered an alternative program using base-2 logarithms:
Symbols/Syntax: S2p is (Right input Minimum (One Plus (input Minus Half)) Pow. Pow is Floor Under Log. Log is 2 With Logarithm. Note that S2p is a hook (g h) where g is a train of forks (f1 g1 h1) where h1 is a fork (f2 g2 h2) with h2 a hook (g3 h3) so that execution is (Pow y) <. (1 + (y - -:(Pow y))).
Explanation: First find the largest power of 2 less than input y. Call it pow. Then calculate 1 plus the difference of y and pow. Call it d. Compare pow and d. Return whichever is smaller.
Examples: For input 9, Log 9 is 3.16993 and Pow 3.16993 is 8. 9--:8 is 5, and 1+5 is 6. Finally, 8<.6 is 6. Using the program for a list of inputs produces the Second-order Josephus sequence:
Comments: EACH is not needed because S2p applies to each atom in a list.
A less efficient but perhaps more readable version is S2p1=:Pow <. 1:+(- -:@Pow).
Comparisons of Programs¶
Now the featured programs will be compared for efficiency in speed and space. First, the following utility programs are needed:
Speed¶
Purpose: Measure execution time.
Symbols/Syntax: Time is 6 Foreign 2. Note that this verb may be used monadically for one execution of an expression (on the right) or dyadically for a number of repeated executions (on the left).
Explanation: Average number of seconds used in executing an expression.
Examples:
Comment: For increased accuracy, increase the left input to Time (which will take longer to return the result).
Space¶
Purpose: Measure execution space.
Symbols/Syntax: Space is 7 Foreign 2.
Explanation: Number of bytes used in executing an expression.
Example:
Fixed Programs¶
Purpose: To replace names of sub-programs with their definitions (for better efficiency).
Symbols/Syntax: Fix is an adverb which requires a verb input (on its left).
Explanation: u f. substitutes primitives in verb u.
Example:
Comment: By choosing the same name here, J2b is reassigned. To compare fixed vs. unfixed versions, use a different name.
Note that a fixed program should speed up. For example, now 1000 Time 'J2b 12' is 0.00068846.
Benchmarks¶
Benchmarks were obtained for fixed programs here using J5.01a running Windows 95 on a Pentium II PC with 256M RAM. The benchmarks are compiled below into tables – one table of average time and space for the "J2" family of programs requiring an input of the power of 2 needed to produce the sequence, and one table for the "S2" family of programs using a list of inputs needed to produce the same sequence:
| Input Program\ |
Time (seconds) 4 |
12 |
20 |
Space (bytes) 4 |
12 |
20 |
|---|---|---|---|---|---|---|
hsJ2 * |
0.0000557 | 0.01378 | 2.058 | 4096 | 1181696 | 168298496 |
J2x |
0.0000411 | 0.01275 | 2.019 | 3200 | 1082624 | 143131904 |
J2t |
0.0000396 | 0.01252 | 1.984 | 2944 | 1082176 | 143131456 |
J2r |
0.0000501 | 0.00278 | 1.017 | 2048 | 328512 | 83886912 |
J2b |
0.0000485 | 0.00069 | 0.348 | 2880 | 197440 | 50332480 |
* Last item omitted in result.
| Input Program\ |
Time (seconds) Natural 31 |
Natural 4095 |
Natural 1048575 |
Space (bytes) Natural 31 |
Natural 4095 |
Natural 1048575 |
|---|---|---|---|---|---|---|
,S2a EACH |
0.0102841 | 860.1 | (days) | 4352 | 215552 | (huge) |
S2b EACH |
0.0015516 | 0.2084 | 55.94 | 3840 | 69312 | 16780992 |
S2 ** |
0.0003800 | 0.0485 | 12.63 | 3072 | 100608 | 25168128 |
S2p |
0.0000635 | 0.0039 | 1.45 | 3840 | 296448 | 75499008 |
** Executed without first item (1) of input.
Comparing these benchmarks indicates that J2b (bits approach) is the fastest program for large inputs. S2b (Base-2 encoding approach) is the most economical in space for large inputs. Overall, the programs in the J2 family are generally faster but increasingly inflexible (always returning nearly a power of 2 number of items); whereas the programs in the S2 family generally consume less space and are completely flexible (allowing any list of inputs).
Note that all J2 programs except hsJ2 work correctly for an input of 0 and that all S2 programs except S2 work correctly for an input of 1 to produce the first item in the Second-order Josephus sequence.
Note also that S2b is the only program which correctly handles the degenerate case of an input of 0, producing the additional leading 1 in the sequence (as in [1]).
Concluding Insights and Programming Challenges¶
Defining and comparing programs for the Second-order Josephus problem prompts several insights. First, logarithms (in S2p) appear much faster than encoding-then-decoding (using u&.#: in S2). Secondly, logarithms may be more productive than base-representations in seeking solutions to the General Josephus problem (which involve killing in intervals of k). Indeed, the work here led to an improved definition of a generalized program (from Peelle [7]):
Further, the reader might consider generalization of Second-order Josephus to interval k, which produces intriguing non-decreasing integer sequences (perhaps difficult to express in closed form). And consider the Third-order Josephus problem. Fourth-order? Nth order? (Not difficult!)
Finally, the programs here lead to a simple strategy for surviving the Second-order Josephus problem for N people:
Calculate p – the largest whole power of 2 less than or equal to N. Start by standing at half p. Move up one more. Now move one further for each person over p, but only up to number p.
For example: If N=9 people, p is 8, so start at 4. Add 1 up to 5. 9-8 is 1, so move 1 further. Stand at 6 (which is less than p).
Another example: If N=30 people, p is 16, so start at 8. Add 1 to get 9. 30-16 is 14, so move from 9 up 14 (but stop at p). Stand at 16.
In closing, challenges for the reader are to program this strategy, to generalize the programs here for any interval, and to seek other approaches to the Second-order Josephus problem.
References¶
[0] Peelle, H.A. "Introduction to Functional Programming in J" (in four parts), Vector, Vol. 13, Nos. 1 – 4, 1996–97
[1] Sloane, N.J.A. Sequence A006165, Online Encylopedia of Integer Sequences, http://www.research.att.com/~njas/sequences
[2] McDonnell, E.E. "At Play with J", Vector, Vol. 18, No. 4, 1992
[3] Peelle, H.A. "Technical Correspondence", Vector, Vol. 19, No. 2, 2002
[4] Graham, Knuth & Patashnik, Concrete Mathematics, Addison-Wesley, Reading, MA 1994
[5] Hui, R.K.W. "Three Combinatoric Puzzles", Vector, Vol. 9, No. 2, 1992
[6] Peelle, H. & Lipp, A. "Problem Solving by Programming: The Josephus Problem (Revisited)", Journal of Computer Science Education, Vol. 12, No. 1, Fall 1997
[7] Peelle, H.A."Josephus Generalized in J", Vector, Vol. 14, No. 2, 1997
Appendix¶
Collection of J programs for Second-order Josephus sequence:
NB. Utility programs
Natural =: }.@i.@>:
Sort =: /:~
Power =: 2&^
Log =: 2&^.
EACH =: "0
each =: &.>
NB. Basic Josephus solution
S =: 1&|.&.#: NB. Origin 1
NB. Simulation Approach
E =: ((<:@[ {. ]) , }.)~ S@# NB. Bantchev
E =: (}:@{. , }.)~ S@#
E =: -. <:@S@# { ]
S2 =: E ^: (<:@#) @ (>:@i.) NB. Bantchev
S2a =: E ^: (<: ` Natural)
NB. Sorting Approach
NB. McDonnell
hsJ2 =: 13 : '/:~(>:i.+/2^i.y.),;(#each+:)2^i.y.'
J2x =: 13 : '/:~(Natural 2^y.),(# +:)2^i.y.'
J2t =: Sort @ (Natural@Power , Copy@Power@i.)
Copy =: # +:
NB. Replication Approach
J2r =: >:@Copies # Natural@Power
Copies =: Power@i. In} Power # 0:
In =: <:@+:@[
J2r1 =: Copies1 # Natural@Power
Copies1 =: >:@Power@i. In1} Power # 1:
In1 =: <:@+:@<:@[
NB. Bits Approach
J2b =: +/\ @ Bits =: 1: , ;@:(Take each)@Power@i.
Take =: +: {. (# 1:)
J2b1 =: +/\ @ Bits1 =: 1: , ;@:(Pairs each)@Power@i.
Pairs =: (# 1:),(# 0:)
J2b2 =: +/\ @ Bits2 =: 1: , ;@:(Boxes each)@Power@i.
Boxes =: > i.@+:
NB. Base-2 Encoding Approach
S2 =: (>:@(1&,@({.+.}.)@}.&.#:))"0 NB. Bantchev
S2b =: Shift &. #:
Shift =: -@Second |. One + Half Min Second
Second =: {.@Rotate1=:1&|.
One =: -@# {. 1:
Half =: # {. 0: , 1: , }.@}.
Min =: *. -.
S2b1 =: (Min1 Pow1) @ #:
Pow1 =: # {. 1:
Min1 =: ] <.&#. Shift1 =: One1 + (-Half1)
One1 =: 1: |. ]
Half1 =: _1: |. ]
NB. Log Approach
S2p =: (] <. 1: + (- -:)) Pow
Pow =: <.&.Log
S2p1 =: Pow <. 1: + (- -:@Pow)
NB. Benchmark Utility Programs
Time =: 6!:2
Space =: 7!:2
Fix =: f.
Howard A. Peelle, Professor of Mathematics and Science Education at the University of Massachusetts, has received a Fulbright Scholar Award to join the Institute for Mathematical Research at the University of Putra Malaysia in Kuala Lumpur where he will use J in teaching mathematics teachers during spring 2003.