91/04/21 < C O P Y > To: Dr. Michael W. Ecker REC, 909 Violet Terrace, Clarks Summit, PA 18411 From: Harry J. Smith, 19628 Via Monte Dr., Saratoga, CA 95070 Enclosure: MS-DOS disk (Josephus). Dear Mike, There are so many interesting challenges in the Jan/Feb/Mar 1991 issue of REC that I don't know where to begin. I have started working on several of them, but have been concentrating on "The Thousand Roman Slaves" problem suggested by Steve Wagler. This is, as you noted, actually a classic known as the Josephus problem. Original Problem: 1000 slaves in a circle, numbered 1 to 1000, are all to be shot except one lucky survivor. The order of shooting is 1, 3, 5, etc., always alternating, and always immediately removing the fallen bodies. Once a body has fallen, it is no longer considered part of the circle for purposes of future counting and alternation. Example, n=6: Shoot 1,3,5,2,6; 4 survives. The General Problem: There is an ordered set of n objects arranged in a circle with object i (1 <= i <= n) in position i. All n objects are selected and removed in a certain order and placed in a new circle with the new position number k beings the order of selection. Object f is selected first. After each selection, m minus 1 of the remaining objects following the one removed are skipped and the next object is then selected. We are interested in the nature of the permutation generated by this process, its fixed elements, and in particular the original position L of the last object selected. Note that m and f can be as low as 1 and can be larger than n. A fast way to solve the original problem is to consider the general problem when m = 2 and f = 1. If n is a power of 2, m = 2 and f = 1, then object n will be the last one selected. First we remove all numbers not divisible by 2. Next remove all not divisible by 2 squared. Eventually only n and n/2 is left and it is n/2's time to get shot. The next step is to realize that when m = 2, if we add 1 to n we will add 2 to L the number of the object that will be selected last. This leads us to the equation: The last object selected L = 2^P - 2(2^P - n) = 2n - 2^P, where 2^P is the next power of 2 greater than or equal to n. For n = 1000 the last object selected L = 1024 - 48 = 2000 - 1024 = 976. The equation L = 2n - 2^P and the statements above can be verified by using the equation given by Prof. Donald E. Knuth in his book The Art of Computer Programming, Vol. 1, Pages 181, problem 31. Knuth always selects object m first, so f = m instead of 1. The result of his equation has to be adjusted by subtracting m - f and corrected by +/-n if out of the range [1, n]. Knuth refers to this as the Flavius Josephus problem in his Index and Glossary. He also has a reference to this problem in Vol. 3 of this set of books. His equation states that the k'th man to be executed, for general m and n, is in position x which may be computed as follows: Set x = km, then repeatedly set x = Int((m(x - n) - 1) / (m - 1)) until x <= n. The x <= n test needs to be done before the first application of the equation. I have included a disk containing 5 programs, Joseph1.Pas through Joseph5.Pas. All allow the operator to specify n, m, f; and computes L. The Program Joseph1 uses the mod function to speed up the solution. This is important when m is large compared to the number of objects r remaining in the circle. The Pascal statement: for i:= 1 to ((m-1) mod r) do ... is used to skip over the next m-1 objects, but actually only skips over (m-1) mod r objects. This improvement was not in Knuth's MIX program *JOSEPHUS PROBLEM on pg 516 of Vol. 1. It is important to consider situations when m is very large, at least as large as (n - 1)!. There are n! different permutations that can be made of an ordered set of n distinct objects. The first object can be selected in n ways the second in n - 1 ways etc. If we consider the general problem with n = 4, we can generate all 24 permutations by allowing m to range from 1 to 6 and allowing f to range from 1 to 4. When n = 5 we cannot generate all 120 permutations, only 60, but m must be allowed to be as large as 12 to do this. Here is a sample output from Joseph1 with n = 8, m = 4, f = 4: Execution order, when object i was selected: 5 4 6 1 3 8 7 2 Order of execution, object # selected on k'th selection: 4 8 5 2 1 3 7 6 The resulting permutation expressed in cyclic notation: (1, 5, 3, 6, 8, 2, 4)(7) n = 8, m = 4, f = 4: Object 6 was selected last! There is 1 fixed element: 7. The execution order shows that 1 was executed 5th, 2 was executed 4th, etc. The order of execution shows that 4 was executed 1st, 8 was 2nd, etc. The permutation expressed in cyclic notation shows that 1 was moved to position 5, 5 moved to 3, 3 to 6, 6 to 8, 8 to 2, 2 to 4, 4 to 1 and 7 was picked 7th. Seven is the only fixed element of the permutation. Joseph2 uses Knuth's equation given above to solve the problem. Knuth did not suggest that this would make an efficient program, and it is much slower than Joseph1. It is given as a verification that Joseph1 is producing correct results. Joseph3 searches for Josephus permutations with many fixed elements. Here is a sample output: n = 25, m = 25, f = 1: 9 last! 6 fixed: 1, 2, 8, 13, 14, 23. n = 59, m = 33, f = 22: 14 last! 7 fixed: 9, 15, 19, 26, 28, 45, 58. n = 90, m = 42, f = 50: 90 last! 8 fixed: 2, 16, 23, 51, 58, 61, 69, 90. n = 232, m = 189, f = 88: 114 last! 9 fixed: 3, 39, 64, 85, 112, 133, 159, 165, 206. n = 1000, m = 54, f = 965: 694 last! 8 fixed: 39, 355, 435, 541, 558, 708, 807, 996. Joseph4 is a graphical solution of the Josephus problem. It shows a display with the n points arranged in a circle. Starting from point 1, each point has a directed line segment drawn from it to the next point to be selected. Joseph5 shows Graphical Orbits in Josephus permutations. It again shows a display with the n points arranged in a circle. Each point i has a directed line segment drawn from its original position i to its new position k resulting from the permutation. This is the most fun program of the set. Start it with n = 1, m = 1, f = 1; and repeatedly press the + on the key pad. The program will progress through various values of the three variables. Sincerely, Harry

Return to Harry's Home Page

This page accessed times since October 20, 2004.

Page created by: hjsmithh@sbcglobal.net

Changes last made on Saturday, 14-May-05 12:48:31 PDT