2024/11/10 by Hikaru Manabe, Ryohei Miyadera, Manabe, Hikaru +7
Computer Science · Mathematics · #91A05 #91A46 #Advanced Mathematical Identities #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Polynomial and algebraic computation
paper · pdf · doi:10.48550/arxiv.2411.16696
openalex publication_date 2024/11/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present a new O(k log n) algorithm of the Josephus problem. The time complexity of our algorithm is O(k log n), and this time complexity is on a par with the existing O(k log n) algorithm. We do not have any recursion overhead or stack overflow because we do not use any recursion. Therefore, the space complexity of our algorithm is O(1), and ours is better than the existing O(k log n) algorithm in this respect. When k is small and n is large, our algorithm is better than the existing O(k log n) algorithm. This new algorithm is based on a relation between the Josephus problem and a maximum Nim of combinatorial game theory.