Fixed Points of the Josephus Function via Fractional Base Expansions

この論文は、ジョセファス関数$J_3$の不動点列と中国剰余定理の関連性を確立し、$3/2$進法におけるその数値パターンを明らかにすることで、不動点の桁を決定する再帰的手順を導出するものである。

要約

🎪 物語の舞台：ヨセフスのパズル

まず、背景にある「ヨセフスの問題」というゲームについてお話ししましょう。

円卓に $n$ 人の人が座っていると想像してください。
1 番から順番に数え、「1、2、3」と数えた**「3」の人を退場させます。そして、残った人の中でまた「1、2、3」と数え、3 番目の人を退場させます。これを最後に1 人だけ**残るまで続けます。

このゲームで「最後に生き残る人」が最初どこに座っていたらいいかを計算する関数が、この論文の主人公である**「ヨセフス関数（$J_3$）」**です。

🔍 研究の目的：「固定点」の正体

このゲームには、ある不思議な性質を持っています。
「もし $n$ 人が座っているとき、生き残る人が $n$ 番目（あるいは $n-1$ 番目）に座っているなら、その $n$ は特別な数字だ！」というルールです。

この論文の著者たちは、この**「特別な数字（固定点）」の列が、実はある「秘密のコード」**で繋がっていることに気づきました。

🧩 発見その 1：中国の剰余定理（パズルのピース）

まず、著者たちはこの「特別な数字」を見つけるために、**「中国の剰余定理」**という数学の道具を使いました。

• 比喩：
  Imagine you have a giant lock with two keys. One key only fits if the number leaves a specific remainder when divided by 3 (like 3, 6, 9...), and the other key only fits if it leaves a specific remainder when divided by 2 (like 2, 4, 6...).
  この論文では、生き残る数字（固定点）を見つけることが、「3 で割った余り」と「2 で割った余り」という 2 つの条件を同時に満たす数字を探すことと同じだとわかりました。
  これにより、複雑な計算が、よりシンプルで論理的なパズルのように解けるようになりました。

🌟 発見その 2：「3/2 進法」という新しい言語

ここがこの論文の最も面白い部分です。

通常、私たちは数を「10 進法（0〜9）」や「2 進法（0 と 1）」で表します。しかし、著者たちは**「3/2 進法」**という、普段使わない不思議な数え方を導入しました。

• どんな数え方？
  普通の 10 進法では「10」は「10」ですが、この「3/2 進法」では、数字の並び方が少し違います。例えば、普通の数字「4」は、この進法では「212」と書かれます（$2 \times (3/2)^2 + 1 \times (3/2)^1 + 2 = 4$ のような計算になります）。
  重要なのは、この進法を使うと、「生き残る数字の並び」に驚くべき規則性が見つかるということです。

🧵 発見その 3：「レゴブロック」のように積み上がる数字

著者たちは、この「3/2 進法」で数字を書き並べると、次の数字は前の数字の後ろに、特定のブロックをくっつけるだけで作れることに気づきました。

• 比喩：
  生き残る数字の列を、レゴブロックで積み上げるゲームだと想像してください。
  • 最初のブロック（数字）が決まっています。
  • 次の数字を作るには、前のブロックの一番右端に、新しいブロックを1 つ、2 つ、あるいは3 つくっつけるだけで完成します。
  • くっつけるブロックの形（「1」だけか、「02」か、「0112」か）は、その前に何人の人が退場したか（論文では $m_\ell$ という値）によって決まります。

つまり、「前の数字の並び」を知っていれば、次の数字の並びを、単に「お尻にブロックを足す」だけで簡単に作れるという、とてもシンプルで美しいルールが見つかったのです。

💡 この研究の意義

この発見は、以下のような意味を持っています。

1. 計算が楽になる：
   これまで巨大な数字を計算して「生き残る人」を見つけるのは大変でしたが、この「ブロックを足すルール」を使えば、前の数字から次の数字を瞬時に作れます。
2. 数学の美しさ：
   一見すると複雑でランダムに見える「ヨセフスの問題」が、実は「3/2 進法」という新しい視点で見ると、非常に整然としたパターンを持っていることがわかりました。
3. 未来への扉：
   この研究は、もっと難しい「4 番目の人を退場させるゲーム（$J_4$）」など、他のバージョンの問題にも応用できるかもしれません。

📝 まとめ

この論文は、**「ヨセフスのパズルで生き残る人を見つけるには、複雑な計算をする必要はない。『3/2 進法』という新しい言語で数字を書き、前の数字の後ろに『レゴブロック』をくっつけるだけで、次の答えが簡単にわかる」**という、驚くほどシンプルで美しいルールを発見したものです。

数学は、難しい計算の積み重ねだけでなく、世界を眺める「新しいメガネ」を見つけることで、隠れた美しさを発見できる分野だということを教えてくれる素晴らしい研究です。

技術概要

論文「分数基底展開によるジョセファス関数の不動点」の技術的サマリー

1. 問題の背景と目的

本論文は、古典的な組み合わせ論の難問である「ジョセファス問題（Josephus problem）」から派生したジョセファス関数 $J_3$ の性質、特にその**不動点（fixed points）**の列 $\{n_p^{(\ell)}\}_{\ell \in \mathbb{N}}$ の構造を解明することを目的としています。

• ジョセファス問題の定義: $n$ 人の人が円卓に座り、1 番から順に数え、2 人をスキップして 3 番目の人を排除するプロセスを繰り返します。最後に残る人の位置を $J_3(n)$ とします。
• 不動点の定義: $J_3(n_e) = n_e$ となる整数 $n_e$ を「高極値点（high extremal point）」の一種である「不動点」と呼びます。
• 既存の知見: 2 人ごとに 1 人を排除するバージョン（$J_2$）では、不動点が $2^{\ell-1}$ で与えられ、2 進数表記において「1」を右に追加する単純な再帰的パターンが存在することが知られています。
• 本研究の課題: $J_3$ の場合、直接計算は計算コストが高く、$J_2$ のような明確な数値パターンや再帰的公式が存在するかが不明でした。本研究では、$J_3$ の不動点列に対して、$J_2$ の 2 進数に相当する**「3/2 進法（base 3/2）」**を用いた分数基底展開を導入し、その数字の並びに潜む再帰的パターンを明らかにすることを目指します。

2. 手法とアプローチ

本研究は、数論的アプローチと分数基底展開の 2 つの主要な手法を組み合わせています。

2.1. 中国剰余定理（CRT）との関連付け

まず、不動点列 $\{n_p^{(\ell)}\}$ の再帰的定義式（文献 [2] の定理 2）を代数的に操作し、隣接する 2 つの不動点 $n_p^{(\ell)}$ と $n_p^{(\ell+1)}$ の間に以下の関係が成り立つことを示しました。
$$2n_p^{(\ell+1)} + 1 \equiv 0 \pmod{3^{m_\ell}}$$
$$3n_p^{(\ell)} + 2 \equiv 0 \pmod{2^{m_\ell}}$$
ここで、$m_\ell$ は 2 つの不動点の間に存在する「純粋な高極値点（pure high extremal points）」の個数です。
この関係式から、各不動点が互いに素な法（$3^p$と$2^q$）を持つ線合同方程式系を満たすことが導かれ、**中国剰余定理（CRT）**を用いて不動点が一意に決定される構造が示されました。また、ベズーの恒等式（Bézout's identity）を用いて、これらの合同式を満たす解の具体的な構成が議論されました。

2.2. 分数基底（3/2 進法）の導入

$J_2$ の 2 進数展開の成功に着想を得て、$J_3$ の解析には基底 3/2 の数値表現が適していると考えました。

• 定義: 自然数 $N$ を以下の形式で表現します。
  $$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]$$
  ここで、各桁 $d_i$ は集合 $\{0, 1, 2\}$ に属します。
• アルゴリズム: 任意の自然数 $N$ に対して、$2N_i = 3N_{i+1} + d_i$（$d_i \equiv 2N_i \pmod 3$）という漸化式を用いて、一意な有限展開（3/2 進展開）を計算するアルゴリズムを提示しました。
• 特徴: 標準的な 3/2 進法（桁が 0, 1 のみ）とは異なり、ここでは桁に「2」を許容することで、すべての自然数が有限桁で表現可能になります。

3. 主要な結果と発見

3.1. 不動点列の 3/2 進展開におけるパターン

最初の 20 個の不動点の 3/2 進展開を計算・分析した結果、以下の驚くべきパターンが発見されました（Table 3 参照）：

1. 接尾辞の継承: 不動点 $n_p^{(\ell)}$ の 3/2 進展開は、次の不動点 $n_p^{(\ell+1)}$ の展開の**先頭部分（初期セグメント）**として現れます。
2. 桁数の増加: $n_p^{(\ell+1)}$ の桁数は、$n_p^{(\ell)}$ の桁数に $m_\ell + 1$ を加えた数になります。
3. 追加される桁の規則: 末尾に追加される桁は、$m_\ell$（純粋な高極値点の数）によって完全に決定されます。

3.2. 主要定理（Theorem 1）

上記の観察を定式化したのが本論文の中心的な成果である定理 1です。
$n_p^{(\ell)} = (\hat{d}_k \dots \hat{d}_0)_{3/2}$ と仮定すると、$n_p^{(\ell+1)}$ の展開は以下のようになります。

• 場合 1 ($m_\ell = 0$):
  $$n_p^{(\ell+1)} = (\hat{d}_k \dots \hat{d}_0 \mathbf{1})_{3/2}$$
  （末尾に「1」を追加）
• 場合 2 ($m_\ell = 1$):
  $$n_p^{(\ell+1)} = (\hat{d}_k \dots \hat{d}_0 \mathbf{02})_{3/2}$$
  （末尾に「02」を追加）
• 場合 3 ($m_\ell \ge 2$):
  $$n_p^{(\ell+1)} = (\hat{d}_k \dots \hat{d}_0 \mathbf{0 \underbrace{1 \dots 1}_{m_\ell-1 \text{ 個}} 2})_{3/2}$$
  （末尾に「0」 followed by $(m_\ell-1)$ 個の「1」 followed by「2」を追加）

この定理により、$J_3$ の不動点列の数字の並びは、単純な文字列操作（接尾辞の追加）によって再帰的に生成できることが証明されました。

4. 意義と今後の展望

4.1. 学術的意義

• 構造の透明化: $J_3$ の不動点の複雑な挙動を、中国剰余定理と分数基底展開という 2 つの強力な数学的ツールを用いて、極めて単純な「桁の追加」という操作として記述することに成功しました。
• 一般化の枠組み: $J_2$ の 2 進数における「1 の連続」というパターンが、$J_3$ の 3/2 進法における「0, 1, 2 の特定の並び」として一般化されたことを示しました。
• 計算の効率化: 大きな $n$ に対する $J_3(n)$ の直接計算は困難ですが、不動点の生成プロセスが明確化されたことで、数列の性質を効率的に解析する道が開かれました。

4.2. 今後の研究課題

論文の結論部分では、以下の 2 つの方向性が示唆されています。

1. $J_4$ への拡張: 4 人ごとに 1 人を排除する $J_4$ において、基底 4/3 の展開を用いて同様の再帰的桁公式が存在するかどうかの検討。ただし、$J_4$ は純粋な高極値点のタイプが 2 種類あるため、より複雑なインデックス管理が必要になる可能性があります。
2. 任意の $n$ に対する $J_3(n)$ の計算: 不動点だけでなく、任意の整数 $n$ の 3/2 進展開から $J_3(n)$ を直接計算できるかという問題。現在の $J_3(n)$ の式は 2 つのインデックスを必要とするため、3/2 進展開との直接的な対応付けにはさらなる研究が必要です。

総じて、本論文は数論的構造と分数基底というユニークな視点を組み合わせることで、古典的な組合せ論の問題に新たな光を当て、その深い構造を解き明かした画期的な研究と言えます。