Maximum Nim and Josephus Problem algorithm

Abstract

In this study, we study a Josephus problem algorithm. Let $n,k$ be positive integers and $g_k(n)=\lfloor \frac{n}{k-1}\rfloor +1$, where $\lfloor \rfloor$ is a floor function. Suppose that there exists $p$ such that $g_k^{p-1}(0)<n(k-1)\le g_k^p(0)$, where $g_k^p$ is the $p$-th functional power of $g_k$. Then, the last number that remains is $nk-h{2}_k^p(0)$ in the Josephus problem of $n$ numbers, where every $k$-th numbers are removed. This algorithm is based on Maximum Nim with the rule function $f_k(n)=\lfloor \frac{n}{k}\rfloor$. Using the present article's result, we can build a new algorithm for Josephus problem.

arXiv admin note: substantial text overlap with arXiv:2403.19308