Maximum Nim and Josephus Problem algorithm

2024/04/09 by Shoei Takahashi, Takahashi, Shoei, Hikaru Manabe +3
Computer Science · #91A05 #91A46 #Combinatorics (math.CO) #Data Management and Algorithms #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph Theory and Algorithms

paper · pdf · doi:10.48550/arxiv.2404.06112

openalex publication_date 2024/04/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this study, we study a Josephus problem algorithm. Let n,k be positive integers and g_k(n) = \lfloor (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) ≤ 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-h2_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 (n)/(k) \rfloor. Using the present article's result, we can build a new algorithm for Josephus problem.

Related

• Maximum Nim and Josephus Problem
• A New 0(klog n) Algorithm for Josephus Problem
• Analytical Study and Efficient Evaluation of the Josephus Function
• Josephus Nim
• On the Recurrence Formula for Fixed Points of the Josephus Function