Josephus problem is rather well known - every $m$-th person in circle of $n$ people is killed - question is where in the circle was the last person standing?

Let us make an inverse of that problem and ask

What is the least step $m$ for which $k$-th person is the last one standing in a circle of $n$ people ($n$ and $k$ are given)?

There are two logical questions to ask:

Does such $m$ always exist? (Conjecture: yes - computer tests show it is correct up to $n=300$).

What is the upper bound for $m$? $\text{lcm}(1,2,\ldots,n)$ seems logical, but is there something lower (computer tests show a number of outliers that make it hard to estimate such a bound).

  • $\begingroup$ See OEIS A198789 and A198790 for small examples $\endgroup$
    – Henry
    May 10, 2012 at 7:18
  • $\begingroup$ Thank you for the reference, Henry - still, I have an even larger table produced with my own and it doesn't really help. $\endgroup$ May 10, 2012 at 7:26

1 Answer 1


Here's the maximum of $m$ over all $k$ for fixed $n$ plotted over $n$ together with $nH_n$, the expectation value for the coupon collector's problem (where $H_n$ is the $n$-th harmonic number):

maximum of m over all k

The fact that the values seem to scatter around this expectation value indicates that it may be a good heuristic to consider the last person standing to be selected uniformly at random, independently for all $m$. If so, the "probability" for there to be any counterexamples beyond $n=1000$ (up to which I tested) should be exceedingly small. It's hard to quantify exactly how small, since the heuristic might not be valid all the way up to $m=\operatorname{lcm}(1,\dotsc,n)$, but even if it's just valid up to $n^2$, the "probability" of someone surviving all $n^2$ attempts on their life would be roughly

$$n\left(1-\frac1n\right)^{n^2}\approx n\mathrm e^{-n}\;,$$

so the expected number of counterexamples beyond $n=1000$ would be roughly

$$\int_{1000}^\infty n\mathrm e^{-n}\mathrm dn=1001\mathrm e^{-1000}\approx5\cdot10^{-432}\;.$$

  • $\begingroup$ The almost linear appearance of $nH_n$ tricked me and made me wonder why is it so - now it makes sense after all! Thank you for the answer. $\endgroup$ May 10, 2012 at 9:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .