Analytical Study and Efficient Evaluation of the Josephus Function
Analytical Study and Efficient Evaluation of the Josephus Function
复制标题
DOI：
10.48550/arxiv.2303.15457
复制
发表时间：
2023-03
期刊：
影响因子：
--
通讯作者：
Yunier Bello-Cruz;Roy Quintero-Contreras
中科院分区：
文献类型：
--
作者：
Yunier Bello-Cruz;Roy Quintero-Contreras
本文提出了一种分析约瑟夫斯函数J_k内禀性质的新方法。充分揭示了$J_{_k}$极值点之间的线性结构，从而设计了计算$J_{_k}（n）$的有效算法。代数表达式，描述如何递归计算极值点，包括不动点，推导。作为结果，证明了所有k\geq 2$的连续极值和不动点的存在性，推广了Knuth关于k=2$的结果。此外，进行了广泛的比较数值实验，以说明所提出的算法的性能相比，已建立的算法评估约瑟夫函数。结果表明，该方法在大输入条件下计算J_{_k}（n）$是高效的.
A new approach to analyzing intrinsic properties of the Josephus function, $J_{_k}$, is presented in this paper. The linear structure between extreme points of $J_{_k}$ is fully revealed, leading to the design of an efficient algorithm for evaluating $J_{_k}(n)$. Algebraic expressions that describe how recursively compute extreme points, including fixed points, are derived. The existence of consecutive extreme and also fixed points for all $k\geq 2$ is proven as a consequence, which generalizes Knuth result for $k=2$. Moreover, an extensive comparative numerical experiment is conducted to illustrate the performance of the proposed algorithm for evaluating the Josephus function compared to established algorithms. The results show that the proposed scheme is highly effective in computing $J_{_k}(n)$ for large inputs.