General Solution for Josephus Problem

Overview of the solution for Josephus problem where every third person is eliminated, followed by a solution for the general case (arbitrary "q" where every q'th person is eliminated).

In addition a short discussion of interesting problem deriving from Josephus Problem.

1. A General Solution to Josephus Problem Yoav Francis July 2007 Topics in Number Theory, 2007/2 COMAS – College of Management – Academic Studies, Rishon Lezion, Israel Overview and Additional Problems

2. Motivation Given , find , where denotes the number of people in the initial circle. Let us first consider the case in which .  

3. Recursive Solution to   Where:  

4. A General Method for   For a group of people, each time we iterate on a person, we can provide him with a new number. In such a scenario – the numbers 1,2 would become . The number 3 would then be killed. 4,5 would become . 6 would be killed, and so on. Finally, would become , and would be killed and so on. Eventually the person denoted as will be the sole survivor.   Illustration for :  

5. A General Method for   The person to be killed is denoted (Example: the 10 th person is numbered “30”, the 9 th is numbered “27” and so on) We can find out who is the survivor if we find the original number of the person numbered (let us mark ) If then the person numbered necessarily had a previous number, which we can find in the following manner: or (Similarly to how we found the next number of and in the previous slide) Thus . The previous number of the person was or – meaning, it was (using )  

6. A General Method for   We have received an algorithm for :  

7. A General Method for   Let us note that this can be somewhat improved. The algorithm is not recursive, neither has a “closed” shape – but still allows us to compute the answer rather quickly for a large . Luckily, we can improve it. Let us define and use it instead of . This change matches numbering from to 1 instead of from to . This yields the following:  

8. A General Method for   We can now write the algorithm in the following manner: This is a much simpler form as enters the computation in a simple manner.  

9. The General Algorithm for Josephus Problem In a matter of fact, we can use the same justifications we used to show that the survivor for (where every person is killed) is computed in the following way:   This is the general algorithm. Let us note that for we’d get in every phase , so for the case of we get:  

10. The General Algorithm for Josephus Problem We can attempt to bring the algorithm to a “nicer” form. It cannot be brought to a closed form (but for the case of ), due to the “ceiling” function that we perform on every phase. However – we can still tidy-up the algorithm. Let us recursively define:   These numbers do not have a “nice” form but for , but if we agree to accept the expression as a “known expression” – then the solution for the general case of the Josephus problem would be:   (Where is the smallest one for which the following holds: )  

11. Additional Problems Derived From Josephus Problem Finding the second-to-last person remaining in Josephus problem (For example, if we want to find the last 2 people standing). Let us denote and get:  

12. Additional Problems Derived From Josephus Problem Another problem: Josephus finds himself in the position . Given that he can choose the “skip factor”( , which should he choose so he stays alive? Let us define and assume that . By Bertrand’s Postulate there exists a prime number . We can also assume that . We’d want to choose a q so the following holds: and:  

13. Additional Problems Derived From Josephus Problem Now, the people who would be removed (“killed”) are: The position would not be killed (we may get but that is still valid for the problem) Example: . Josephus got and will decide: (This holds for the 2 requirements of ). LCM(1,….,10) = 2520  

14. Thanks