View source for Josephus problem

{{Short description|Mathematical counting-out question}}
[[File:Josephus_problem_41_3.svg|thumb|upright=1.3|[[Claude Gaspar Bachet de Méziriac]]'s interpretation of the Josephus problem with 41 soldiers and a step size of 3, showing that places 16 and 31 are last to be killed &ndash; time progresses inwards along the spiral, green dots denoting live soldiers, grey dead soldiers, and crosses killings]]
In [[computer science]] and [[mathematics]], the '''Josephus problem''' (or '''Josephus permutation''') is a theoretical problem related to a certain [[counting-out game]].  Such games are used to pick out a person from a group, e.g. [[eeny, meeny, miny, moe]].

[[File:JosephusProblemDrawing.png|thumb|right|A drawing for the Josephus problem sequence for 500 people and skipping value of 6. The horizontal axis is the number of the person. The vertical axis (top to bottom) is time (the number of cycle). A live person is drawn as green, a dead one is drawn as black.<ref name=formulae.org />]]

In the particular counting-out game that gives rise to the Josephus problem, a number of people are standing in a [[circle]] waiting to be executed. Counting begins at a specified point in the circle and proceeds around the circle in a specified direction. After a specified number of people are skipped, the next person is executed. The procedure is repeated with the remaining people, starting with the next person, going in the same direction and skipping the same number of people, until only one person remains, and is freed.

The problem—given the number of people, starting point, direction, and number to be skipped—is to choose the position in the initial circle to avoid execution.

==History==
The problem is named after [[Flavius Josephus]], a [[Jew]]ish historian and leader who lived in the 1st century. According to Josephus's firsthand account of the [[siege of Yodfat]], he and his 40 soldiers were trapped in a cave by [[Roman soldiers]]. They chose suicide over capture, and settled on a serial method of committing suicide by drawing lots. Josephus states that by luck or possibly by the hand of God, he and another man remained until the end and surrendered to the Romans rather than killing themselves. This is the story given in Book 3, Chapter 8, part 7 of Josephus's ''[[The Jewish War]]'' ([[Illeism|writing of himself in the third person]]):

{{blockquote|However, in this extreme distress, he was not destitute of his usual sagacity; but trusting himself to the providence of God, he put his life into hazard [in the manner following]: "And now," said he, "since it is resolved among you that you will die, come on, let us commit our mutual deaths to determination by lot. He whom the lot falls to first, let him be killed by him that hath the second lot, and thus fortune shall make its progress through us all; nor shall any of us perish by his own right hand, for it would be unfair if, when the rest are gone, somebody should repent and save himself." This proposal appeared to them to be very just; and when he had prevailed with them to determine this matter by lots, he drew one of the lots for himself also. He who had the first lot laid his neck bare to him that had the next, as supposing that the general would die among them immediately; for they thought death, if Josephus might but die with them, was sweeter than life; yet was he with another left to the last, whether we must say it happened so by chance, or whether by the providence of God. And as he was very desirous neither to be condemned by the lot, nor, if he had been left to the last, to imbrue his right hand in the blood of his countrymen, he persuaded him to trust his fidelity to him, and to live as well as himself.|source={{harvnb|Josephus|n.d.|p=579|loc=Wars of the Jews, Book III, Ch. 8, para 7}} }}

The details of the mechanism used in this feat are rather vague. According to James Dowdy and Michael Mays,{{sfn|Dowdy|Mays|1989|page=125}} in 1612 [[Claude Gaspard Bachet de Méziriac]] suggested the specific mechanism of arranging the men in a circle and counting by threes to determine the order of elimination.{{sfn|Bachet|1612|p=174}} This story has been often repeated and the specific details vary considerably from source to source. For instance, [[Israel Nathan Herstein]] and [[Irving Kaplansky]] (1974) have Josephus and 39 comrades stand in a circle with every seventh man eliminated.{{sfn|Herstein|Kaplansky|1974|pp=121-126}} A history of the problem can be found in S. L. Zabell's ''Letter to the editor'' of the ''[[Fibonacci Quarterly]]''.{{sfn|Zabell|1976|pp=48, 51}}

As to intentionality, Josephus asked: “shall we put it down to divine providence or just to luck?”<ref name=Cohen>Cohen, Richard.  ''[https://books.google.com/books?id=Cw02EAAAQBAJ&pg=PT54 Making History: The Storytellers Who Shaped the Past]'', p. 54 (Simon & Schuster 2022).</ref>  But the surviving Slavonic manuscript of Josephus tells a different story: that he “counted the numbers cunningly and so managed to deceive all the others”.<ref name=Cohen /><ref>{{cite book|contribution-url=https://gustavus.edu/mcs/max/concrete-abstractions-pdfs/chapter3.pdf|contribution=3.5 An Application: The Josephus Problem|pages=65–67|title=Concrete Abstractions: An Introduction to Computer Science Using Scheme|url=https://gustavus.edu/academics/departments/mathematics-computer-science-and-statistics/max/concrete-abstractions.html|year=1999|first1=Max|last1=Hailperin|first2=Barbara|last2=Kaiser|first3=Karl|last3=Knight|publisher=Brooks/Cole Publishing Company}}</ref>  Josephus had an accomplice; the problem was then to find the places of the two last remaining survivors (whose conspiracy would ensure their survival). It is alleged that he placed himself and the other man in the 31st and 16th place respectively (for {{mvar|k}} = 3 below).{{sfn|Rouse Ball|1905|p=19}}

==Variants and generalizations==
[[File:Josephus_problem_30_9.svg|thumb|Variant of the Josephus problem with 30 people and a step size of 9 &ndash; time progresses inwards along the spiral, green dots denoting live soldiers, grey dead soldiers, and crosses killings]]
A medieval version of the Josephus problem involves 15 Turks and 15 Christians aboard a ship in a storm which will sink unless half the passengers are thrown overboard. All 30 stand in a circle and every ninth person is to be tossed into the sea. The Christians need to determine where to stand to ensure that only the Turks are tossed.{{sfn|Newman|1988|pp=2403–2405}} In other versions the roles of Turks and Christians are interchanged.

{{harvnb|Graham|Knuth|Patashnik|1989|p=8}} describe and study a "standard" variant: Determine where the last survivor stands if there are {{mvar|n}} people to start and every second person ({{mvar|k}} = 2 below) is eliminated.

A generalization of this problem is as follows. It is supposed that every {{mvar|m}}th person will be executed from a group of size {{mvar|n}}, in which the {{mvar|p}}th person is the survivor.  If there is an addition of {{mvar|x}} people to the circle, then the survivor is in the {{math|''p'' + ''mx''}}-th position if this is less than or equal to {{math|''n'' + ''x''}}.  If {{mvar|x}} is the smallest value for which {{math|''p'' + ''mx'' > ''n'' + ''x''}}, then the survivor is in position {{math|(''p'' + ''mx'') − (''n'' + ''x'')}}.{{sfn|Robinson|1960|pp=47–52}}

==Solution==
[[File:Josephus_problem_table.svg|thumb|link={{filepath:Josephus_problem_table.svg}}|Penultimate (pink) and ultimate (ultramarine) places in the Josephus problem for various group size, ''n'' and step size, ''k''. In [{{filepath:Josephus_problem_table.svg}} the SVG file,] hover over the values to show the full order of killing.]]
In the following, <math>n</math> denotes the number of people in the initial circle, and <math>k</math> denotes the count for each step, that is, <math>k-1</math> people are skipped and the <math>k</math>-th is executed. The people in the circle are numbered from <math>1</math> to <math>n</math>, the starting position being <math>1</math> and the counting being [[Counting#Inclusive counting|inclusive]].

===''k'' = 2===
The problem is explicitly solved when every second person will be killed (every person kills the person on their left or right), i.e. <math>k=2</math>. (For the more general case <math>k\neq 2</math>, a solution is outlined below.)
The solution is expressed [[recursive]]ly. Let <math>f(n)</math> denote the position of the survivor when there are initially {{mvar|n}} people (and <math>k=2</math>).
The first time around the circle, all of the [[parity (mathematics)|even]]-numbered people die.
The second time around the circle, the new 2nd person dies, then the new 4th person, etc.; it is as though there were no first time around the circle.

If the initial number of people were even, then the person in position {{mvar|x}} during the second time around the circle was originally in position <math>2x - 1</math> (for every choice of {{mvar|x}}). Let <math>n=2j</math>. The person at <math>f(j)</math> who will now survive was originally in position <math>2f(j) - 1</math>. This yields the [[recurrence relation|recurrence]]

:<math>f(2j) = 2f(j)-1\;.</math>

If the initial number of people were [[parity (mathematics)|odd]], then person 1 can be thought of as dying at the end of the first time around the circle. Again, during the second time around the circle, the new 2nd person dies, then the new 4th person, etc.
In this case, the person in position {{mvar|x}} was originally in position <math>2x+1</math>. This yields the recurrence

:<math>f(2j+1) = 2f(j)+1\;.</math>

When the values are tabulated of <math>n</math> and <math>f(n)</math> a pattern emerges ({{OEIS2C|A006257}}, also the leftmost column of blue numbers in the figure above):

{| class="wikitable" style="text-align: center;"
!{{mvar|n}}
| 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12 || 13 || 14 || 15 || 16
|-
!<math>f(n)</math>
| 1 || 1 || 3 || 1 || 3 || 5 || 7 || 1 || 3 ||  5 ||  7 ||  9 || 11 || 13 || 15 ||  1
|}

This suggests that <math>f(n)</math> is an [[Sequence#Increasing and decreasing|increasing]] odd sequence that restarts with <math>f(n)=1</math> whenever the index ''n'' is a [[power of 2]].
Therefore, if ''m'' and {{mvar|l}} are chosen so that <math>n = 2^m+l</math> and <math>0 \leq l < 2^m</math>, then <math>f(n) = 2l + 1</math>.
It is clear that values in the table satisfy this equation. Or it can be thought that after {{mvar|l}} people are dead there are only <math>2^m</math> people and it goes to the <math>2l+1</math>st person. This person must be the survivor. So <math>f(n) = 2l+1</math>. Below, a [[mathematical proof|proof]] is given by [[mathematical induction|induction]].

'''Theorem:''' If <math>n = 2^m+l</math> and <math>0 \leq l < 2^m</math>, then <math>f(n) = 2l+1</math>.

'''Proof:''' The [[strong induction]] is used on {{mvar|n}}. The base case <math>n=1</math> is true.
The cases are considered separately when {{mvar|n}} is even and when {{mvar|n}} is odd.

If {{mvar|n}} is even, then choose <math>l_1</math> and <math>m_1</math> such that <math>n/2 = 2^{m_1}+l_1</math> and <math>0\leq l_1 < 2^{m_1}</math>. Note that <math>l_1 = l/2</math>.
<math>f(n) = 2f(n/2)-1=2((2l_1)+1) - 1=2l+1</math> is had where the second equality follows from the induction hypothesis.

If {{mvar|n}} is odd, then choose <math>l_1</math> and <math>m_1</math> such that <math>(n-1)/2 = 2^{m_1}+l_1</math> and <math>0\leq l_1 < 2^{m_1}</math>. Note that <math>l_1 = (l-1)/2</math>.
<math>f(n) = 2f((n-1)/2)+1=2((2l_1)+1) + 1=2l+1</math> is had where the second equality follows from the induction hypothesis. This completes the proof.

{{mvar|l}} can be solved to get an explicit expression for <math>f(n)</math>:

:<math>f(n) = 2(n-2^{\lfloor \log_2(n) \rfloor})+1</math>

The most elegant form of the answer involves the [[binary representation]] of size {{mvar|n}}: <math>f(n)</math> can be obtained by a one-bit left cyclic shift of {{mvar|n}} itself. If {{mvar|n}} is represented in binary as <math>n = 1 b_1 b_2 b_3\dots b_m</math>, then the solution is given by <math>f(n)=b_1 b_2 b_3 \dots b_m 1</math>. The proof of this follows from the representation of {{mvar|n}} as <math>2^m+l</math> or from the above expression for <math>f(n)</math>.

'''Implementation: ''' If {{mvar|n}} denotes the number of people, the safe position is given by the function <math>f(n) = 2l+1</math>, where  <math>n=2^m+l</math> and <math>0\leq l<2^m</math>.

Now if the number is represented in binary format, the first bit denotes <math>2^m</math> and remaining bits will denote {{mvar|l}}. For example, when {{tmath|1=n=41}}, its binary representation is:

 n    = 1   0   1   0   0   1
 2<sup>m</sup>   = 1   0   0   0   0   0
 l    =     0   1   0   0   1
<syntaxhighlight lang="java">
/**
 * @param n the number of people standing in the circle
 * @return the safe position who will survive the execution 
 *   f(N) = 2L + 1 where N =2^M + L and 0 <= L < 2^M
 */
public int getSafePosition(int n) {
	// find value of L for the equation
	int valueOfL = n - Integer.highestOneBit(n);
	return 2 * valueOfL  + 1;
}
</syntaxhighlight>

==== Bitwise ====
The easiest way to find the safe position is by using [[bitwise operator]]s. In this approach, shifting the most-significant set bit of {{mvar|n}} to the least significant bit will return the safe position.<ref name=github.com /> Input must be a positive [[integer]].

 n    = 1   0   1   0   0   1
 n    = 0   1   0   0   1   1
<syntaxhighlight lang="java">
/**
 * @param n (41) the number of people standing in the circle
 * @return the safe position who will survive the execution 
 */
public int getSafePosition(int n) {
    return ~Integer.highestOneBit(n*2) & ((n<<1) | 1);
    //     ---------------------- ---  | ------------
    //     Get the first set bit   |   | Left Shift n and flipping the last bit
    //    and take its complement  |   |
    //                             |   |
    //                Multiply n by 2  |
    //                         Bitwise And to copy bits exists in both operands.
}
</syntaxhighlight>

===''k'' = 3===
In 1997, Lorenz Halbeisen and [[:de:Norbert_Hungerbühler|Norbert Hungerbühler]] discovered a [[closed-form solution|closed-form]] for the case <math>k=3</math>. They showed that there is a certain constant

:<math>\alpha \approx 0.8111...</math>

that can be computed to arbitrary precision. Given this constant, choose {{mvar|m}} to be the greatest integer such that <math>\operatorname{round}(\alpha \cdot (3/2)^m) \le n</math> (this will be either <math>m^\prime = \operatorname{round}(\log_{3/2} n/\alpha)</math> or <math>m^\prime - 1</math>). Then, the final survivor is

:<math>f(n) = 3(n - \operatorname{round}(\alpha \cdot (3/2)^m)) +  (2</math> if is rounded up else <math>1)</math>

for all <math>n \ge 5</math>.

As an example computation, Halbeisen and Hungerbühler give <math>n = 41, k = 3</math> (which is actually the original formulation of Josephus' problem). They compute:

:<math>m^\prime \approx \operatorname{round}(\log_{3/2} 41/0.8111) \approx \operatorname{round}(9.68) = 10</math>
:<math>\operatorname{round}(\alpha \cdot (3/2)^{m^\prime}) \approx \operatorname{round}(0.8111 \cdot (3/2)^{10}) = 47</math> and therefore <math>m = 9</math>
:<math>\operatorname{round}(0.8111 \cdot (3/2)^9) \approx \operatorname{round}(31.18) = 31</math> (note that this has been rounded down)
:<math>f(n) = 3(41 - 31) + 1 = 31</math>

This can be verified by looking at each successive pass on the numbers {{val|1}} through {{val|41}}:

:{{nowrap|1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26, 28, 29, 31, 32, 34, 35, 37, 38, 40, 41}}
:{{nowrap|2, 4, 7, 8, 11, 13, 16, 17, 20, 22, 25, 26, 29, 31, 34, 35, 38, 40}}
:{{nowrap|2, 4, 8, 11, 16, 17, 22, 25, 29, 31, 35, 38}}
:{{nowrap|2, 4, 11, 16, 22, 25, 31, 35}}
:{{nowrap|2, 4, 16, 22, 31, 35}}
:{{nowrap|4, 16, 31, 35}}
:{{nowrap|16, 31}}
:{{val|31}}

===The general case===
[[Dynamic programming]] is used to solve this problem in the general case by performing the first step and then using the solution of the remaining problem. When the index starts from one, then the person at <math>s</math> shifts from the first person is in position <math>((s-1)\bmod n)+1</math>, where {{mvar|n}} is the total number of people. Let <math>f(n,k)</math> denote the position of the survivor. After the <math>k</math>-th person is killed, a circle of <math>n-1</math> remains, and the next count is started with the person whose number in the original problem was <math>(k\bmod n)+1</math>. The position of the survivor in the remaining circle would be <math>f(n-1,k)</math> if counting is started at <math>1</math>; shifting this to account for the fact that the starting point is <math>(k\bmod n)+1</math> yields the recurrence{{sfn|Park|Teixeira|2018|pp=1-7}}

: <math>f(n,k) = ((f(n-1,k)+k-1) \bmod n)+1,\text{ with }f(1,k)=1\,,</math>

which takes the simpler form

: <math>g(n,k) = (g(n-1,k)+k) \bmod n,\text{ with }g(1,k)=0</math>

if the positions are numbered from <math>0</math> to <math>n-1</math> instead.

This approach has [[Big-O notation|running time]] <math>O(n)</math>, but for small <math>k</math> and large <math>n</math> there is another approach. The second approach also uses dynamic programming but has running time <math>O(k\log n)</math>. It is based on considering killing ''k''-th, 2''k''-th, ..., <math>(\lfloor n/k \rfloor k)</math>-th people as one step, then changing the numbering.{{Citation needed|date=April 2016}}

This improved approach takes the form

:<math>g(n,k) = \begin{cases}
0 & \text{if } n=1\\
(g(n-1,k)+k) \bmod n & \text{if } 1 < n < k\\
    \begin{Bmatrix}
    g(n- \left \lfloor \frac{n}{k} \right \rfloor,k)-n \bmod k + n & \text{if } g(n- \left \lfloor \frac{n}{k} \right \rfloor,k)< n \bmod k \\
     \lfloor \frac{k(g(n- \left \lfloor \frac{n}{k} \right \rfloor,k)-n \bmod k) }{k-1} \rfloor & \text{if } g(n- \left \lfloor \frac{n}{k} \right \rfloor,k) \ge n \bmod k
    \end{Bmatrix}  & \text{if } k \le n\\
\end{cases}
 </math>

==See also==
* [[FLAMES (game)]]

==References==
===Citations===
{{reflist|refs=

<ref name=formulae.org>{{cite web |url=https://formulae.org/?example=Josephus_problem |title=Josephus problem in Fōrmulæ programming language |first=Laurence |last = R.Ugalde |website=Fōrmulæ |access-date=July 26, 2021}}</ref>

<ref name=github.com>{{cite web |title=Josephus Problem using Bitwise Operation (Java) |url=https://gist.github.com/a6y3ap/0b552ac514d6f83a34f44dc3c0301f62 |website=GitHub |access-date=January 7, 2018 |date=January 7, 2018}}</ref>

}}

===Sources===
{{refbegin|2|indent=yes}}
*{{cite book |last=Bachet |first=C. G. |year=1612 |title=Problemes Plaisants ed Delectables qui se font par les Nombres |language=fr|trans-title=}}
*{{cite book |last1=Graham |first1=R. L. |last2=Knuth |first2=D. E. |author-link2=Donald Knuth |last3=Patashnik |first3=O. |year=1989 |title=Concrete Mathematics: A Foundation for Computer Science |publisher=Addison Wesley |isbn=978-0-201-14236-5 }}
*{{cite book |last1=Herstein |first1=I. N. |last2=Kaplansky |first2=I. |year=1974 |title=Matters Mathematical |url=https://archive.org/details/mattersmathemati00hers/page/121 |url-access=registration |publisher=Harper and Row |isbn=9780060428037 }}
*{{cite book|author-link=|first=Flavius |last=Josephus|title= The works of Flavius Josephus: in three volumes; with illustrations |chapter=|translator= William Whiston|url =https://archive.org/details/worksofflaviusjo1873jose/page/578/mode/2up|date=n.d.|publisher=George Routledge & Sons|location=London }}
*{{cite book |last=Newman |first=J. R. |author-link=James R. Newman |year=1988 |title=The World of Mathematics |volume=4 |publisher=Tempus}}
*{{cite journal|first1=Jang-Woo|last1=Park|first2=Ricardo|last2=Teixeira|title=Serial execution Josephus Problem|year=2018|journal=Korean J. Math|doi=10.11568/kjm.2018.26.1.1|volume=26|number=1|pages=1–7}}
*{{cite journal|first1=W. J. |last1=Robinson|title=The Josephus problem|journal=Math. Gaz.|year=1960|volume=44|number=347|pages=47–52|doi=10.2307/3608532|jstor=3608532|s2cid=125735054 }}
*{{cite book |last1=Rouse Ball |first1=W. W. |year=1905|title=Mathematical Recreations and Essays |edition=2nd |publisher=Macmillan|location=London |url=https://www.gutenberg.org/ebooks/26839}}
*{{cite journal|last=Zabell|first=S. L.|year=1976|title=Letter to the editor|url=https://www.fq.math.ca/Issues/14-1.pdf|journal=Fibonacci Quarterly|volume=14|pages=48–51|doi=10.1080/00150517.1976.12430596 }}
{{refend}}

===Further reading===
{{refbegin|2|indent=yes}}
*{{cite book |last1=Cormen |first1=Thomas H. |author-link1=Thomas H. Cormen |last2=Leiserson |first2=Charles E. |author-link2=Charles E. Leiserson |last3=Rivest |first3=Ronald L. |author-link3=Ronald L. Rivest |last4=Stein |first4=Clifford |author-link4=Clifford Stein |year=2001 |title=[[Introduction to Algorithms]] |edition=Second |chapter=Chapter 14: Augmenting Data Structures |publisher=MIT Press and McGraw-Hill |isbn=0-262-03293-7 |page=318}}
*{{cite journal |last1=Dowdy |first1=James |last2=Mays |first2=Michael E. |year=1989 |title=Josephus Permutations |journal=Journal of Combinatorial Mathematics and Combinatorial Computing |volume=6 |pages=125–130|url=https://www.researchgate.net/publication/266756060}}
*{{cite journal|first1=L. |last1=Halbeisen|first2=N. |last2=Hungerbühler|title= The Josephus Problem|journal= J. Théor. Nombres Bordeaux |year=1997|volume=9|number=2|pages=303–318|doi=10.5802/jtnb.204|url=http://www.numdam.org/item/JTNB_1997__9_2_303_0|doi-access=free}}
*{{cite journal|first1=F.|last1=Jakóbczyk |title=On the generalized Josephus problem|journal=Glasow Math. J.|year=1973|volume=14|number=2|pages=168–173 | doi=10.1017/S0017089500001919|s2cid=122980022 |doi-access=free}}
*{{cite journal|first1=Errol L.|last1=Lloyd|title= An O(n logm) algorithm for the Josephus Problem|journal=J. Algor. |year=1983|volume=4|number=3|pages=262–270 |doi=10.1016/0196-6774(83)90025-1}}
*{{cite web |last1=Mount |first1=John |title=Dudeney's Catching The Mice Puzzle |url=https://win-vector.com/2024/10/11/dudeneys-catching-the-mice-puzzle/ |website=Win Vector Blog |date=11 October 2024 |publisher=Win Vector LLC |access-date=12 October 2024}}
*{{cite journal|first1=Andrew M.|last1=Odlyzko|first2=Herbert S.|last2=Wilf | title=Functional iteration and the Josephus problem|journal =Glasgow Math. J. |year=1991|volume=33|number=2|pages=235–240|doi=10.1017/S0017089500008272|s2cid=123160551 |doi-access=free}}
*{{cite book|first1=Frank |last1=Ruskey |first2=Aaron | last2=Williams|chapter= The Feline Josephus Problem|title = Lect. Not. Comp. Sci.|series=Lecture Notes in Computer Science |volume=6099|year=2010|pages=343–354|doi=10.1007/978-3-642-13122-6_33|bibcode=2010LNCS.6099..343R |isbn=978-3-642-13121-9 }} FUN2010
*{{cite journal|first1=Frank|last1=Ruskey|first2=Aaron|last2=Williams |s2cid=2273820|title=The Feline Josephus Problem|journal= Theory Comput. Syst.|year=2012 | volume=50 |pages=20–34|doi=10.1007/s00224-011-9343-6|citeseerx=10.1.1.157.2956}}
*{{cite arXiv|first1=Shaun |last1=Sullivan|first2=Erik|last2=Insko|eprint=1803.11340|title=A variant on the Feline Josephus Problem|year=2018|class=math.CO}}
*{{cite journal|first1=Nicolas|last1=Theriault|year=2001|journal=Util. Math. |number=58 |pages=161–173|title=Generilazations of the Josephus Problem|citeseerx=10.1.1.164.2015}}
*{{cite journal |last1=Woodhouse |first1=David  |year=1973 |title=The extended Josephus problem |journal= Rev. Mat. Hisp.-Amer. |volume=33 | number=4| pages=207–218}}
{{refend}}

==External links==
* [http://www.cut-the-knot.org/recurrence/flavius.shtml Josephus Flavius game] (Java Applet) at [[cut-the-knot]] allowing selection of every n<sup>th</sup> out of 50 (maximum).
* {{MathWorld|JosephusProblem|Josephus Problem}}
* {{YouTube|id=uCsD3ZGzMgE|title=The Josephus Problem - Numberphile}}
* [https://www3.cs.stonybrook.edu/~nbanati/josephus_problem.pdf Generalized Josephus Problem]

[[Category:Combinatorics]]
[[Category:Computational problems]]
[[Category:Josephus]]
[[Category:Mathematical problems]]
[[Category:Permutations]]