Inverse Josephus problem

Question

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

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

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}\;.$$