Fixed Points of the Josephus Function via Fractional Base Expansions

This paper establishes a connection between the fixed points of the Josephus function $J_3$ and the Chinese Remainder Theorem, then utilizes a non-standard fractional base $3/2$ expansion to identify digit patterns that enable a recursive procedure for determining these fixed points.

The Gist

Imagine a game of musical chairs, but with a twist. You have a circle of people, and every time the music stops, you count three people and kick the third one out. You keep doing this until only one person is left standing. This is the famous Josephus Problem.

The big question is: Where should you sit to be the last one standing?

In math terms, if there are $n$ people, the answer is a function called $J_3(n)$. Usually, if you sit in spot $n$, you get kicked out. But sometimes, if you sit in spot $n$, you actually win. These special "lucky seats" are called Fixed Points.

This paper is like a detective story where the authors try to find a secret code that predicts these lucky seats for the "skip two, kill three" version of the game. Here is how they cracked the case, explained simply:

1. The "Magic Number" Connection (Chinese Remainder Theorem)

First, the authors realized that these lucky seats aren't random. They are like pieces of a puzzle that fit together perfectly.

Think of the lucky seats as numbers that have to satisfy two different rules at the same time:

• Rule A: "When you divide me by a certain power of 3, I leave a specific remainder."
• Rule B: "When you divide me by a certain power of 2, I leave a different specific remainder."

The authors used an ancient mathematical tool called the Chinese Remainder Theorem. Imagine you have two different locks (one with 3 teeth, one with 2 teeth). The lucky seat is the only key that fits both locks perfectly. By understanding how these locks work together, they could predict exactly where the next lucky seat would be.

2. The Weird "Fractional" Number System (Base 3/2)

This is the most creative part. Usually, we count in Base 10 (digits 0–9) or Base 2 (digits 0 and 1, like computers).

The authors decided to try counting in Base 3/2.

• The Analogy: Imagine a currency system where a "dollar" is worth 1.5 "cents."
• In this weird system, you can use the digits 0, 1, and 2.
• It sounds confusing, but it's like a special language that speaks directly to the Josephus game.

When they wrote the lucky seats in this "Base 3/2" language, a beautiful pattern emerged. It's like looking at a family tree and realizing that every child looks exactly like their parent, just with a few extra features added to the end.

3. The "Appendage" Rule (The Recursive Pattern)

The paper's biggest discovery is a simple rule for how to get from one lucky seat to the next.

Imagine the lucky seats are a chain of beads.

• The Parent: Take the lucky seat number $n$. Write it in this special Base 3/2 code.
• The Child: To find the next lucky seat, you don't need to recalculate the whole thing. You just take the parent's code and stick a few extra beads on the end.

How many beads do you add? That depends on a "gap number" (called $m$) between the two seats.

• If the gap is small, you add a simple "1".
• If the gap is medium, you add "0, 2".
• If the gap is big, you add a string like "0, 1, 1, 1, 2".

The Metaphor:
Think of the lucky seats as a growing plant.

• The first lucky seat is a seed.
• To grow the next one, you don't start from scratch. You take the existing plant and graft a new branch onto the end.
• The size of the new branch depends on how much "space" (the gap $m$) is between the old plant and the new one.

Why Does This Matter?

Before this paper, finding the next lucky seat was like trying to guess the next number in a sequence by trial and error. It was slow and messy.

Now, the authors have given us a recipe:

1. Look at the current lucky seat.
2. Count the gap to the next one.
3. Just add the specific "tail" to the end of the number.

This turns a complex, hard-to-solve puzzle into a simple, step-by-step game of "add a digit."

The Big Picture

The authors also hinted at the future. They found this pattern for the "skip 2, kill 3" game. They wonder if a similar pattern exists for "skip 3, kill 4" (which would use a Base 4/3 system).

In summary: The paper takes a confusing, ancient puzzle about people in a circle, translates it into a weird language (Base 3/2), and discovers that the solution is actually just a simple game of "copy the parent and add a tail." It turns a chaotic math problem into a predictable, rhythmic dance.

Technical Summary

Here is a detailed technical summary of the paper "Fixed Points of the Josephus Function via Fractional Base Expansions" by Yunier Bello-Cruz and Roy Quintero-Contreras.

1. Problem Statement

The paper investigates the Josephus function $J_3(n)$, which determines the position of the survivor in a variation of the classical Josephus problem where every third person is eliminated ($k=3$).

• Context: While the function $J_2(n)$ (eliminating every second person) has a well-known explicit solution and a simple recursive structure for its fixed points (where $J_2(n) = n$), the behavior of $J_3(n)$ is significantly more complex.
• Goal: The authors aim to characterize the sequence of fixed points of $J_3$, denoted as $\{n_p^{(\ell)}\}_{\ell \in \mathbb{N}}$, where $J_3(n_p^{(\ell)}) = n_p^{(\ell)}$. Specifically, they seek a recursive procedure to determine the digits of these fixed points when represented in a specific non-standard number system.

2. Methodology

The authors employ a multi-faceted approach combining combinatorial number theory, modular arithmetic, and non-standard positional number systems.

A. Connection to the Chinese Remainder Theorem (CRT)

The authors first establish a link between the fixed points and the Chinese Remainder Theorem.

• They utilize a known recursive formula for the fixed point sequence involving an integer parameter $m_\ell$ (the count of "pure high extremal points" between consecutive fixed points).
• By manipulating the recurrence relation, they derive a system of linear congruences satisfied by consecutive fixed points $n_p^{(\ell)}$ and $n_p^{(\ell+1)}$:
  $$\begin{cases} 2x_1 + 1 \equiv 0 \pmod{3^{m_\ell}} \\ 3x_2 + 2 \equiv 0 \pmod{2^{m_{\ell+1}}} \end{cases}$$
• Since the moduli $3^{m_\ell}$and$2^{m_{\ell+1}}$ are coprime, the CRT guarantees a unique solution modulo their product. This allows the authors to express fixed points as solutions to systems involving Bézout's identity.

B. Introduction of Base 3/2 Expansion

To simplify the characterization of these fixed points, the authors introduce a fractional base system in base $3/2$.

• Definition: Unlike the standard base $3/2$system (which typically uses digits${0, 1}$), this paper defines a system where any positive integer$N$ is represented as:
  $$N = \frac{1}{2} \left[ d_k \left(\frac{3}{2}\right)^k + \dots + d_1 \left(\frac{3}{2}\right)^1 + d_0 \right]$$
  where the digits $d_i \in \{0, 1, 2\}$.
• Algorithm: A four-step algorithm is provided to compute this expansion uniquely for any integer $N$. The process involves iteratively solving $2N_i = 3N_{i+1} + d_i$with$d_i \equiv 2N_i \pmod 3$.

3. Key Contributions and Results

A. Structural Pattern in Base 3/2

The primary contribution is the discovery of a recursive pattern in the base $3/2$expansions of consecutive fixed points. By analyzing the first 20 fixed points, the authors identified that the expansion of$n_p^{(\ell+1)}$is formed by appending specific digit strings to the expansion of$n_p^{(\ell)}$.

Theorem 1 (Main Result):
Let $n_p^{(\ell)} = (\hat{d}_k \dots \hat{d}_0)_{3/2}$. The expansion of the next fixed point $n_p^{(\ell+1)}$ is determined by the integer $m_\ell$ (the number of pure high extremal points between them) as follows:

1. If $m_\ell = 0$: Append the digit 1.
   $$n_p^{(\ell+1)} = (\hat{d}_k \dots \hat{d}_0 1)_{3/2}$$
2. If $m_\ell = 1$: Append the digits 0, 2.
   $$n_p^{(\ell+1)} = (\hat{d}_k \dots \hat{d}_0 0 2)_{3/2}$$
3. If $m_\ell \ge 2$: Append the digit string 0, followed by $(m_\ell - 1)$ ones, and finally a 2.
   $$n_p^{(\ell+1)} = (\hat{d}_k \dots \hat{d}_0 \underbrace{0 \underbrace{1 \dots 1}_{m_\ell-1} 2}_{\text{total } m_\ell+1 \text{ digits}})_{3/2}$$

B. Digit Count Relationship

The paper proves that the total number of digits in the base $3/2$expansion of$n_p^{(\ell+1)}$is exactly the number of digits in$n_p^{(\ell)}$plus$m_\ell + 1$.

C. Generalization of $J_2$ Results

This work generalizes the known results for $J_2$. In the $J_2$ case, fixed points are $2^{\ell}-1$, which in binary are simply strings of ones ($11\dots1$). The$J_3$result extends this "appending" logic to a fractional base with a more complex digit-appendition rule dependent on the extremal point count$m_\ell$.

4. Significance and Future Directions

• Theoretical Insight: The paper provides a transparent, recursive method to generate the fixed points of $J_3$ without computing the entire Josephus elimination process. It bridges the gap between the discrete dynamics of the Josephus problem and the algebraic structure of fractional base representations.
• Computational Efficiency: The derived recursive formula allows for the direct construction of the digits of large fixed points, bypassing computationally expensive simulations of the elimination process.
• Open Problems:
  1. Direct Computation of $J_3(n)$: Can the base $3/2$expansion of an arbitrary$n$be used to compute$J_3(n)$directly (analogous to the bit-shift property of$J_2$)?
  2. Extension to $J_4$: The authors hypothesize that fixed points for $J_4$ (eliminating every 4th person) might admit a recursive digit formula in base $4/3$. However, they note that$J_4$ has two distinct types of extremal points, suggesting a more complex indexing system may be required.

Conclusion

Bello-Cruz and Quintero-Contreras successfully characterize the fixed points of the Josephus function $J_3$ by linking them to the Chinese Remainder Theorem and revealing a precise recursive structure in their base $3/2$ expansions. This work transforms the understanding of these fixed points from a sequence defined by complex recurrence relations to a sequence defined by simple digit-appendition rules in a fractional base.