Collatz 猜想（3n+1 問題）研究報告

1. 問題陳述

1.1 原始形式

定義 Collatz 映射 \( T: \mathbb{N} \to \mathbb{N} \)：

• 若 \( n \) 為偶數：\( T(n) = n/2 \)
• 若 \( n \) 為奇數：\( T(n) = 3n + 1 \)

Collatz 猜想：對所有正整數 \( n \)，反覆施用 \( T \) 最終到達 1。

1.2 壓縮形式

定義壓縮 Collatz 映射 \( S: \mathbb{N}_{\text{odd}} \to \mathbb{N}_{\text{odd}} \)（奇數到奇數）：

其中 \( v_2(m) \) 是 \( m \) 的 2-adic 賦值（\( m \) 被 2 整除的最大次數）。

等價猜想：對所有奇數 \( n > 1 \)，反覆施用 \( S \) 最終到達 1。

1.3 已知結果

2. 框架一：Epoch 分解與位移座標

2.1 尾隨 1-bit 結構

定義：奇數 \( n \) 的「尾隨 1-bit 數」\( t = v_2(n+1) \)，即 \( n \) 的二進位表示中末尾連續 1 的個數。

寫成 \( n = 2^t m' - 1 \)，其中 \( m' \) 為奇數。

2.2 核心公式

定理（精確公式）：若奇數 \( n \) 有 \( t \) 個尾隨 1-bit，則前 \( t-1 \) 步壓縮 Collatz 映射（每步 \( v_2 = 1 \)）之後：

證明：

定義 \( T(n) = (3n+1)/2 \)（\( v_2 = 1 \) 的壓縮步驟）。

歸納法：

• \( T^1(n) = (3n+1)/2 \)
• \( T^j(n) = (3^j n + c_j)/2^j \)，其中 \( c_j \) 滿足 \( c_j = 3c_{j-1} + 2^{j-1} \)

解遞推：\( c_1 = 1 \)，\( c_j = 3^j - 2^j \)（可直接驗證）。

所以

驗證：\( n = 7 = 111_2 \)，\( t = 3 \)，\( m' = 1 \)。

\( T^2(7) = (3/2)^2 \cdot 8 - 1 = \tfrac{9}{4} \cdot 8 - 1 = 18 - 1 = 17 \)。

實際：\( 7 \to 11 \to 17 \)。✓

2.3 位移座標

定義：\( x = n + 1 \)。

在位移座標下，\( t-1 \) 步「壞步」段是純粹的縮放：

精確等式，無誤差項。

2.4 Epoch 分解

將軌道分解為一系列 epoch：

其中 \( w_i = v_2(3^{t_i} m'_i - 1) \geq 1 \)。

2.5 下降條件

軌道下降的條件化簡為：

等價地，壓縮步驟的平均 \( v_2 \) 必須超過 \( \log_2 3 \approx 1.585 \)。

2.6 隨機遊走模型

取對數後，軌道成為隨機遊走：

其中 \( d_k \) 是 epoch 末步的 \( v_2 \) 值。

• \( E[\text{步幅}] = 2\log(3/2) - 2\log 2 = 2\log(3/4) < 0 \)（負漂移）
• 猜想等價於此遊走對所有初始條件都趨向 \( -\infty \)

3. 框架二：3 態轉換器與譜間隙

3.1 轉換器構造

\( 3n + 1 = n + 2n + 1 \) 在二進位中是逐位加法加進位。進位傳播構成有限狀態轉換器。

位置 i 的計算：

sum = b_i(n) + b_{i-1}(n) + δ_{i,0} + carry_{i-1}
output_bit = sum mod 2
carry_i = sum ÷ 2

進位 \( \in \{0, 1\} \)，結合上一輸入位 \( b_{i-1} \in \{0, 1\} \)，等效為 4 態自動機。

合併等效態後得到 3 態：

3.2 轉移規則

A --0→ A (out 0)     A --1→ B (out 1)
B --0→ A (out 1)     B --1→ C (out 0)
C --0→ B (out 0)     C --1→ C (out 1)

3.3 v₂ 與轉換器的關係

初始狀態（位置 0 特殊處理 +1）：carry₀ = 1, prev = 1 → 狀態 C。

v₂(3n+1) 由首次非零輸出位的位置決定：

3.4 譜間隙計算

對均勻隨機輸入位，3 態轉移矩陣為：

特徵多項式：

因式分解：\( (\lambda - 1)(2\lambda - 1)(2\lambda + 1) = 0 \)

結果：

穩態分佈：\( \pi = (1/3, 1/3, 1/3) \)。

3.5 譜間隙的含義

carry 狀態以速率 \( (1/2)^t \) 收斂到穩態分佈。處理 \( t \) 個隨機輸入位後，carry 的分佈距穩態的距離 \( \leq (1/2)^t \)。

3.6 對 v₂ 去相關性的推論

\( S(n) \) 的低位元是 \( n \) 的高位區段經 carry 濾波的結果。carry 混合（譜間隙 1/2）意味著 \( S(n) \) 的低位與 \( n \) 的低位之間的相關性指數衰減。

4. 框架三：log₂3 的連分數收斂子

4.1 連分數展開

log₂3 的連分數展開為：

這個展開是無限不循環的（因為 log₂3 是超越數）。每一個部分商（partial quotient）\( a_i \) 產生一個收斂子 \( p_i/q_i \)，交替地從上方和下方逼近 log₂3。

4.2 收斂子表

4.3 與 Collatz 最壞情況的關聯

實驗發現：在所有測試的 \( k \) 值（\( k = 5 \) 到 \( k = 44 \)，涵蓋 14 位到 44 位整數），最壞情況的下降比率 \( B/T \) 幾乎全部精確等於 65/41。

這是 \( \log_2 3 \) 的第 6 個連分數收斂子（上方最近的）。

4.4 為什麼 65/41 是天然屏障

• \( \log_2 3 \) 是無理數（由 Gelfond-Schneider 定理，它甚至是超越數）
• 因此不存在整數 \( B, T \) 使得 \( B/T = \log_2 3 \)
• 下降所需的最小整數 \( B = \lceil T \cdot \log_2 3 \rceil \) 永遠嚴格超過臨界值
• 對 \( T = 41 \)：\( \lceil 41 \times 1.58496 \rceil = 65 \)，且 \( 65/41 = 1.5854 > \log_2 3 \)

4.5 數值驗證

\( 2^{64} < 3^{41} < 2^{65} \)：

所以 \( (T, B) = (41, 65) \) 的下降門檻 \( N_0 = 3^{41}/(2^{65} - 3^{41}) \approx 87 \)。

含義：對所有 \( n > 87 \) 且命中 \( (41, 65) \) 窗口的數，\( S^{41}(n) < n \)。

5. 框架四：序數值勢函數

5.1 靈感來源：Goodstein 定理

Goodstein 定理：Goodstein 序列在 PA（皮亞諾算術）中不可證其終止，但用 \( < \varepsilon_0 \) 的序數歸納即可證明。

Goodstein 的技巧是把自然數的「hereditary base-n 表示」對應到序數，然後利用序數的良基性（well-foundedness）來證明下降。我們嘗試對 Collatz 做類似的事。

5.2 Block 結構與序數賦值

為每個奇數 \( n \) 定義序數 \( \alpha(n) \)，基於 \( n \) 的二進位 block 結構：

其中 \( 1^{b_i} \) 表示連續 \( b_i \) 個 1-bit，\( 0^{a_i} \) 表示連續 \( a_i \) 個 0-bit。奇數 \( n \) 一定以 1 結尾，所以最低位的 block 一定是 1-block。

嘗試賦值：

這裡 \( k \) 是 1-block 的數量（即序數的「層級」），\( b_i \) 是第 \( i \) 個 1-block 的長度。直覺上，block 數量越多、序數越「高」。

5.3 斷裂點：block 數量可以增加

乘 3 加 1 可以增加 block 數量——進位穿過 0-block 會產生新的分界。

例如：\( n = 27 = 11011_2 \)（2 個 1-block），經過 Collatz 步驟後可能產生更多 1-block。沒有簡單的序數映射能單調遞減，因為 block 結構的演化不具有 Goodstein 式的層級遞減特徵。

5.4 有限修正函數方法

嘗試構造勢函數 \( V(n) = \log_2 n + g(n \bmod 2^k) \)：

• 對 \( k = 2 \)（mod 4 修正）：\( n \equiv 7 \pmod{8} \) 時 \( g(n) - g(T(n)) = 0 > 0.585 \) 不成立
• 對 \( k = 3 \)（mod 8 修正）：\( n \equiv 15 \pmod{16} \) 時同樣失敗
• 一般性結論：\( n \equiv -1 \pmod{2^j} \)（任意多尾隨 1-bit）永遠創造不可修復的問題

定理：不存在基於有限位修正的勢函數（形如 \( \log n + g(n \bmod 2^k) \)）能對所有奇數 \( n > 1 \) 單調遞減。

證明：\( n \equiv -1 \pmod{2^{k+1}} \) 的數有 \( k \) 個連續 \( v_2 = 1 \) 步，累積增長 \( (3/2)^k \)。有限修正函數 \( g \) 最多提供 \( O(1) \) 的補償，不足以抵消 \( (3/2)^k \) 的指數增長。\( \square \)

6. 框架五：反向樹與密度論證

6.1 反向 Collatz 樹

定義樹 \( \mathcal{T} \)，根為 1。每個奇數 \( m \) 的前驅（standard mapping, NOT compressed）：

猜想等價於 \( \mathcal{T} \) 覆蓋所有正整數——如果每個正整數都出現在這棵樹上，表示所有數的 Collatz 軌道最終都會抵達 1。

6.2 「遺漏集」的性質

若遺漏集 \( S = \mathbb{N}_{\text{odd}} \setminus \mathcal{T} \neq \emptyset \)，則 \( S \) 必須滿足：

1. 正向不變：\( S(S) \subseteq S \)——遺漏集中的數經過 Collatz 步驟後仍留在遺漏集中。
2. 自然密度為 0：由 Tao (2019) 的結果，幾乎所有正整數的 Collatz 軌道都趨近任意小的值。遺漏集的密度必為 0。
3. 包含完整 2-tower：若奇數 \( n \in S \)，則 \( \{n, 2n, 4n, 8n, \ldots\} \) 全部屬於 \( S \)（偶數版本的完整倍數塔）。

7. 框架六：ℤ₂ 上的 ×3 混合性

7.1 2-adic 遍歷性

在 \( \mathbb{Z}_2 \)（2-adic 整數）上，乘以 3 是一個保測自同構。

對 Haar 測度幾乎所有 \( x \)，上述集合在 \( (\mathbb{Z}/2^m\mathbb{Z})^\times \) 中均勻分佈。具體而言，\( 3 \) 在模 \( 2^m \) 的乘法群中的階恰好是 \( 2^{m-2} \)（對 \( m \geq 3 \)），因此 \( 3 \) 的冪次遍歷了恰好一半的奇數殘基。

7.2 與 Collatz 的連接

Collatz 映射在 \( \mathbb{Z}_2 \) 上連續且良定義。遍歷性意味著 \( v_2 \) 序列的經驗分佈趨向幾何分佈（均值 2）：

直觀理解：如果 \( \times 3 \) 的混合性夠強，那麼 \( 3n + 1 \) 的末尾位元看起來就像「隨機」的——恰好有 \( 1/2 \) 的機率末尾是 0（即被 2 整除），\( 1/4 \) 的機率末尾兩位是 00，以此類推。這就是幾何分佈 \( \text{Geo}(1/2) \)。

8. 框架七：Kolmogorov 複雜度與資訊論

8.1 觀察

正整數 \( n \) 的 Kolmogorov 複雜度 \( K(n) \leq \log_2 n + O(1) \)。

發散軌道 \( S^T(n) \to \infty \) 意味著 \( \log_2 S^T(n) \to \infty \)，但：

所以發散軌道的數值高度可壓縮——它們的位元長度不斷增長，但描述它們所需的資訊量卻只有 \( O(\log n + \log T) \)。

8.2 嘗試

可壓縮數（低 Kolmogorov 複雜度）具有結構化的位元模式。carry 攪動應破壞此結構。

直觀理解：如果一個數的二進位表示高度規律（例如很多連續的 0 或 1），那麼乘以 3 再加 1 時的進位（carry）傳播會把這些規律「打亂」。但問題是——打亂到什麼程度？

9. 計算實驗

9.1 實驗一：每個位元長度 k 的最壞情況平均 v₂

完整枚舉所有 \( k \)-位奇數（\( k \leq 18 \)），計算 descent 軌跡的平均 \( v_2 \)。

關鍵發現：最壞情況的 B/T 比率穩定在 \( 65/41 = 1.5854 \)，始終 \( > \log_2 3 = 1.5850 \)。

9.2 實驗二：Mersenne 數 \( (2^k - 1) \) 的軌道

所有 Mersenne 數均到達 1，平均 \( v_2 \) 始終 \( > \log_2 3 \)。

9.3 實驗三：大 k 值的最壞情況搜尋

使用智慧抽樣（Mersenne + 尾隨 1 模式 + 前輪最壞擴展 + 隨機），搜尋 \( k = 5 \) 到 \( k = 44 \)。

結果：所有測試的 \( k \) 值中，最壞情況的 B/T 始終 \( \geq 65/41 > \log_2 3 \)。

偶見 \( B/T = 149/94 \approx 1.5851 \)（\( k = 19, 29, 31 \)），這是 \( 65/41 \) 和 \( 84/53 \) 的中位分數，仍 \( > \log_2 3 \)。

9.4 實驗四：累積比率 \( R(T) = \Sigma v_2 / (T \cdot \log_2 3) \)

• 全局最小 \( R = 1/\log_2 3 \approx 0.6309 \)，總是出現在第 1 步（\( v_2 = 1 \)）
• \( R \) 在初始壞步段下降，之後回升
• 最終 \( R \) 始終 > 1（軌道始終最終下降）

9.5 實驗五：v₂ = 1 比例的 Expander Mixing 驗證

即使 \( v_2 = 1 \) 的比例高達 68%，偶發的大 \( v_2 \)（3, 6）足以補償：

n = 154079 的 v₂ 分佈（41 步下降軌跡）：
  v₂=1: 28 步 (68.3%)
  v₂=2:  5 步 (12.2%)
  v₂=3:  7 步 (17.1%)
  v₂=6:  1 步 (2.4%)
  總和: 28 + 10 + 21 + 6 = 65 = B  ✓

一次 \( v_2 = 6 \) 的步驟補償了 5 次 \( v_2 = 1 \) 的損失。

9.6 實驗六：v₂ 序列可視化

Mersenne 數的 \( v_2 \) 序列示例：

2⁸-1 = 255:    111111163331234
2¹²-1 = 4095:  11111111111511111211322212321215122312242111111243331234
2²⁰-1:         111111111111111111152125132232212251111113146422312412241123

可見：初始長串 \( v_2=1 \)（尾隨 1-bit 造成），然後出現 \( v_2 \geq 2 \) 的補償步驟。

9.7 互動實驗場

以下提供六個互動實驗，可自行調整參數，即時觀察計算結果。

10. 等價化約鏈

10.1 下降引理 D

10.2 引理 D ⇒ Collatz 猜想

步驟一（無非平凡循環）：

假設存在循環 \( \{c_1 < c_2 < \cdots < c_P\} \)。取最小元 \( c_1 \)。引理 D 說存在 \( k \) 使得 \( S^k(c_1) < c_1 \)。但 \( S^k(c_1) \) 在循環中，所有元素 \( \geq c_1 \)。矛盾。\( \square \)

步驟二（無發散軌道）：

從 \( n \) 出發，由引理 D 得 \( n_1 = S^{k_1}(n) < n \)。再由引理 D 得 \( n_2 = S^{k_2}(n_1) < n_1 \)。嚴格遞減的正奇數序列 \( n > n_1 > n_2 > \cdots \) 由 \( \mathbb{N} \) 的良序性必終止於 1。\( \square \)

10.3 引理 D 的算術等價

\( S^T(n) < n \) 等價於 \( B_T > T \cdot \log_2 3 \)，其中 \( B_T = \sum_{i=1}^T v_i \)。

精確表述：

若 \( B_T > T \cdot \log_2 3 \)：\( 2^{B_T} > 3^T \)，故左邊 \( > 0 \)，右邊 \( > 0 \)。對充分大的 \( n \)（\( n > C_T/(2^{B_T} - 3^T) \)）成立。

10.4 逆向

Collatz 猜想 ⇒ 引理 D 是平凡的（軌道到 1 途中必有下降）。

因此：引理 D ⇔ Collatz 猜想。

11. 有界軌道分析

11.1 有界軌道 → 循環

證明：軌道是有限集 \( \{m \in \mathbb{N}_{\text{odd}} : n \leq m \leq M\} \) 中的序列，由鴿巢原理必重複。\( \square \)

11.2 循環方程

壓縮 Collatz 映射的 \( P \)-循環 \( S^P(m) = m \)：

其中 \( C = \sum_{j=0}^{P-1} 3^{P-1-j} \cdot 2^{B - B_{j+1}} > 0 \)。

11.3 循環蘊含 \( 2^B > 3^P \)

由 \( C > 0 \) 和 \( m > 0 \)：\( 2^B - 3^P > 0 \)，即 \( 2^B > 3^P \)，即 \( B > P \cdot \log_2 3 \)。

由 \( \log_2 3 \) 是無理數（超越數，Gelfond-Schneider 定理）：\( 2^B \neq 3^P \) 對所有正整數 \( B, P \)。

所以 \( 2^B - 3^P \geq 1 \)（它們是不同的正整數）。

11.4 循環元素的上界

\( m = C/(2^B - 3^P) \)。

11.5 未解決部分

12. 結構性障礙分析

12.1 三重不可通約性

Collatz 映射同時涉及三種不可通約的數學結構：

12.2 所有框架的共同失敗模式

每個框架都能處理這三種結構中的一到兩種，但在第三種面前失敗：

12.3 核心不可化約的困難

所有路線最終都化約為同一個陳述：

此陳述等價於 Collatz 猜想本身，因此不構成「簡化」。

13. 結論

13.1 本研究的貢獻

1. 精確公式 \( T^{t-1}(n) = (3/2)^{t-1}(n+1) - 1 \)：在位移座標 \( x = n+1 \) 下，壞步段是純粹的乘以 \( (3/2)^{t-1} \)。
2. 3 態轉換器模型：將 Collatz 映射的 carry 傳播化約為 3 態自動機 \( \{A, B, C\} \)。
3. 譜間隙 = 1/2：精確計算轉移矩陣的特徵值 \( \{1, 1/2, -1/2\} \)。
4. 65/41 收斂子屏障：實驗發現最壞情況的 B/T 比率精確命中 \( \log_2 3 \) 的第 6 個連分數收斂子。
5. 等價化約：引理 D（某個窗口 \( B/T > \log_2 3 \)）\( \Leftrightarrow \) Collatz 猜想。
6. 有界情形分析：有界軌道 → 循環 → \( 2^B > 3^P \)（由 \( \log_2 3 \) 的無理性）。
7. 計算驗證：對所有 \( k \leq 18 \)（完整枚舉）和 \( k \leq 44 \)（抽樣），最壞情況始終滿足 \( B/T > \log_2 3 \)。

13.2 未解決的部分

1. 無非平凡循環：已知 \( m = C/(2^B - 3^P) \)，但無法無條件證明此方程在正整數中無解。
2. 無發散軌道：需要排除 \( B_T/T \to \log_2 3 \)（從下方）的軌道，這要求一個尚不存在的確定性 Expander Mixing 定理。

13.3 最終判斷

本研究從多個角度攻擊此問題，建立了新的分析框架，但所有路線最終收斂至同一結構性障礙：Collatz 映射同時混合了乘法、加法和二進位三種不可通約的數學結構，而目前數學中不存在能同時處理這三者的統一框架。

14. 附錄：程式碼與符號索引

14.1 主實驗程式

功能：

• 實驗 1：每個位元長度 k 的最壞情況平均 v₂
• 實驗 2：Mersenne 數 (2^k − 1) 的軌道分析
• 實驗 3：Expander Mixing 驗證（v₂=1 比例分佈）
• 實驗 4：滑動窗口 v₂ 分析
• 實驗 5：累積比率 \( R(T) = \Sigma v_2 / (T \cdot \log_2 3) \) 的軌跡
• 實驗 6：所有 k-位奇數的最小累積比率

14.2 深度分析程式

功能：

• 分析 1：\( \log_2 3 \) 的連分數收斂子計算
• 分析 2：大 k 值最壞情況搜尋（智慧抽樣）
• 分析 3：危險軌道的逐步分析
• 分析 4：最壞情況 B/T 比率 vs 連分數收斂子對應
• 分析 5：每個步數 T 的最小下降所需 B
• 分析 6：全軌道最小累積比率分佈

14.3 符號索引

14.4 參考文獻

• Tao, T. (2019). Almost all orbits of the Collatz map attain almost bounded values. arXiv:1909.03562
• Eliahou, S. (1993). The 3x+1 problem: new lower bounds on nontrivial cycle lengths. Discrete Mathematics
• Conway, J. H. (1972). Unpredictable iterations. Proc. 1972 Number Theory Conf.
• Lagarias, J. C. (2010). The Ultimate Challenge: The 3x+1 Problem. AMS.