On the recurrence formula for fixed points of the Josephus function
The Josephus function, denoted by \( J_k ( n ) \), can be defined as the position of the last survivor among \( n \) people arranged in a circle when every \( k \)-th person is eliminated repeatedly.\N\NIt is well known that \N\[\NJ_2 ( n ) = 2 ( n - 2^{\lfloor \log_2 ( n ) \rfloor} ) + 1,\N\]\Nbut a general closed-form expression for \( J_k ( n ) \) has not yet been found (the existence of such an expression is however guaranteed by Mazzanti's theorem, since \( J_k ( n ) \) is clearly a bivariate Kalmár elementary function).\N\NIn this article, the authors give recurrence formulas for the extremal points and the fixed points of \( J_3 ( n ) \) (see Lemma 1 and Theorem 2). However, the main contribution can be written as \N\[\NJ_3 ( n ) = 3 n + 1 - ( 2 / 3 )^{m - t} ( 3 / 2 )^m ( 3 f + 2 ),\N\]\Nwhere \( f \) is the least fixed point that upper-bounds \( n \) (i.e., the least integer \( f \geq n \) such that \( J_3 ( f ) = f \)), \( m \) is the dyadic valuation of \( 3 f + 2 \), and \N\[\Nt = \lceil \log_{3 / 2} ( ( 2 n + 1 ) / ( 3 f + 2 ) ) \rceil\N\]\N(see Theorem 3). This identity provides a faster method for computing \( J_3 ( n ) \) than the extremal algorithm introduced in the authors' previous work, [J. Integer Seq. 27, No. 3, Article 24.3.8, 20 p. (2024; Zbl 1541.11026)], as it seems to require approximately half the iterations (see Subsection 2.1). Furthermore, it clearly simplifies to \N\[\NJ_3 ( n ) = 3 n + 1 - ( 3 f + 2 ) ( 3 / 2 )^t\N\]\N(in particular, the value \( m \) is no longer necessary), although it is unclear whether the authors were aware of this fact.
- An application of Fourier transforms on finite abelian groups to an enumeration arising from the Josephus problem
- Analytical Study and Efficient Evaluation of the Josephus Function
- Functional iteration and the Josephus problem
- General solution to the spectator-first Tantalizer problem
- scientific article; zbMATH DE number 4135942 (Why is no real title available?)
- scientific article; zbMATH DE number 3599973 (Why is no real title available?)
- scientific article; zbMATH DE number 718142 (Why is no real title available?)
- scientific article; zbMATH DE number 1178976 (Why is no real title available?)
- Image encryption using the chaotic Josephus matrix
- On the generalization of Josepus's problem.
- On the generalized Josephus problem
- Permuting operations on strings and their relation to prime numbers
- Problèmes plaisants et délectables qui se font par les nombres. Quatrième édition revue et simplifiée.
- The Josephus problem
This page was built for publication: On the recurrence formula for fixed points of the Josephus function
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6943830)
