# Inverse Josephus problem

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).

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

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):
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}\;.$$
• 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. May 10 '12 at 9:43