collatz-m4m6 ツール仕様レポート

バージョン: 0.2.0 | 日付: 2026-02-07 | 言語: Rust (edition 2021)

1. 概要

コラッツ型写像 \(T(n) = (xn+1)/2^d\) の m4/m6 ペア述語分解に基づく走査・解析ツール。論文「コラッツ型写像 \((xn+1)/2^d\) のペア述語分解と \(3n+1\) の構造的閉鎖性」のアルゴリズム 7.1 の実装であり、以下の機能を提供する。

任意の \(xn+1\) 型写像（\(x-1\) が2の冪）に対する1ステップ走査
軌道追跡（1に到達するまでの全ステップ記録）
区間検証（停止時間法による大量数値の並列検証）
GPK (Generate/Propagate/Kill) 統計の集約・可視化
GUI による対話的操作

2. 対応パラメータ

パラメータ \(x\)	\(s = \log_2(x-1)\)	参照パターン	状態
3	1（奇数）	ref_R=(a[i-1], b[i]), ref_L=(b[i], a[i])	専用最適化あり
5	2（偶数）	ref_R=(b[i-1], b[i]), ref_L=(a[i-1], a[i])	専用最適化あり
9	3（奇数）	汎用パターン	汎用ルーチン
17	4（偶数）	汎用パターン	汎用ルーチン
33, 65, 129, …	5, 6, 7, …	汎用パターン	汎用ルーチン

制約: \(x \geq 3\) かつ \(x-1\) が2の冪であること。

3. アーキテクチャ

3.1 モジュール構成

src/
├── lib.rs            # クレートルート（公開API定義）
├── main.rs           # CLI エントリポイント
├── gui.rs            # GUI エントリポイント（egui）
├── pair_number.rs    # PairNumber 型（m4/m6 ビットペア表現）
├── reference.rs      # 参照パターン（表3.1の実装）
├── scan.rs           # 1ステップ走査（GPK分類含む）
├── postprocess.rs    # 後処理（MSBトリミング、末尾ゼロ除去、再ペア化）
├── trajectory.rs     # 軌道追跡・停止時間計算
└── verify.rs         # 区間並列検証（rayon）

3.2 データフロー

入力 n (BigUint)
    │
    ├─ [軌道追跡パス] ─── PairNumber 変換 → scan::collatz_step → postprocess → 記録
    │                     （各ステップの m4/m6, GPK 列, d を保持）
    │
    └─ [停止時間パス] ─── u128 直接演算 → BigUint フォールバック
                          （PairNumber を経由せず高速演算、GPK はビット抽出で計算）

3.3 二重パス設計

	軌道追跡パス	停止時間パス
用途	単発解析（GUI 単発タブ）	区間検証（GUI 区間タブ）
内部表現	PairNumber (Vec<u8> per bit)	u128 / BigUint 直接演算
GPK 取得	scan 関数の副産物（各ペアの GPK 列）	ビット列から直接計算（統計のみ）
出力	全ステップの n', d, GPK 列	停止時間 + GPK 集約統計
速度	遅い（研究用詳細データ）	高速（大量検証用）

4. 停止時間高速パス

4.1 `stopping_time_u64_fast`

u64 入力に対する最適化パス。

Phase 1: u128 演算

current * x + 1 を u128 で計算
trailing_zeros() で \(d\) を取得、右シフト
GPK は u128 のビットから直接分類
オーバーフロー閾値: (u128::MAX - 1) / x

Phase 2: BigUint フォールバック

u128 オーバーフロー時に自動遷移
BigUint::*=, +=, >>= によるインプレース演算
GPK は to_bytes_le() からビット抽出

4.2 `stopping_time_with_gpk`

BigUint 入力に対する汎用パス。Phase 2 と同一ロジック。

4.3 安全制限

制限	値	目的
MAX_PAIR_COUNT	10,000 ペア	軌道追跡パスのメモリ制限
MAX_BIT_LENGTH	20,000 ビット	停止時間パスのビット長制限
max_steps	GUI で設定可能	発散系列の打ち切り

5. GPK 統計

5.1 分類規則

各ペア位置 \(i\) について、参照パターンに基づく4ビット \((p_r, q_r, p_l, q_l)\) から：

m6段: g_mid = p_r & q_r,  p_mid = p_r ^ q_r
m4段: g_out = p_l & q_l,  p_out = p_l ^ q_l
直列合成: G_i = g_out | (p_out & g_mid)
          P_i = p_out & p_mid
          K_i = それ以外

5.2 キャリー連鎖長

初期キャリー \(c=1\) からの連鎖と、G で再生成された後の連鎖の最大長を記録。ヒストグラム（距離 0–127）として集約。

5.3 実測 GPK 分布（\(n \leq 10^7\), max_steps=500）

	\(3n+1\)	\(5n+1\)	\(17n+1\)
G%	38.41	36.91	37.26
P%	28.32	25.45	25.09
K%	33.26	37.64	37.65
G/K 比	1.15	0.98	0.99

6. GUI 仕様

6.1 構成

フレームワーク: egui (eframe 0.29) + egui_plot 0.29
日本語フォント: Yu Gothic / MS Gothic / Meiryo（自動検出）
ウィンドウサイズ: 900 × 700

6.2 トップパネル

要素	説明
`x =`	\(xn+1\) のパラメータ。\(x-1\) が2の冪の値のみ受理
`max_steps:`	最大反復ステップ数。デフォルト 10000
タブ切替	単発解析 / 区間解析 / 解析

6.3 単発解析タブ

1ステップ実行: \(n\) に対して1回の \((xn+1)/2^d\) を実行。\(n'\), \(d\), GPK 列, carry 連鎖長を表示
軌道追跡: 1到達（または max_steps/ビット長上限）まで反復。バックグラウンドスレッドで実行
- キャンセル可能（停止ボタン）
- 進捗表示（ステップ数, 桁数）200ms 間隔で更新
- 結果: ステップ数, \(\Sigma d\), 最大値桁数, GPK 統計, 軌道先頭100ステップ
- CSV + サマリ TXT を自動保存

6.4 区間解析タブ

範囲指定: 開始値–終了値の全奇数を検証
並列処理: rayon による自動並列化（u64 範囲はチャンク分割）
進捗バー: 100数値ごとに更新、nums/s 表示
キャンセル可能
結果: 検証数, 収束判定, 最大停止時間, GPK 統計, GPK 分布グラフ, キャリー連鎖長グラフ
サマリ TXT を自動保存

6.5 解析タブ

output/ ディレクトリのログファイル一覧を表示
ファイル選択でパラメータ・GPK 統計・グラフを再表示
ログファイル形式を自動パース

7. 出力ファイル

7.1 保存先

exe と同一ディレクトリの output/ フォルダ（自動作成）。

7.2 ファイル命名規則

gui_trace_{x}n1_{n}[_stopped]_{timestamp}.txt     # 軌道追跡サマリ
gui_trace_{x}n1_{n}.csv                            # 軌道追跡 CSV
gui_verify_{x}n1_{start}-{end}[_stopped]_{timestamp}.txt  # 区間検証サマリ

7.3 サマリファイル形式

# collatz-m4m6 verify
range = [3, 9999999]
x = 5
total_checked = 4999999
all_converged = false
max_stopping_time = 490
max_stopping_time_n = 4580349

# GPK
G = 17746659852
P = 12236187544
K = 18094218711
total_pairs = 48077066107
total_steps = 897149444
G% = 36.9129
P% = 25.4512
K% = 37.6359

# Carry chain histogram
0: 720342
1: 1400349
...

elapsed = 79.0672604s

7.4 CSV 形式（軌道追跡）

step,n,d,digits,gpk,G,P,K,max_carry_chain
0,27,0,2,,0,0,0,0
1,41,1,2,PGP,1,2,0,2
...

8. ビルド

8.1 前提条件

Rust toolchain (stable)
MSYS2 MinGW64（Windows の場合、egui のネイティブ依存）

8.2 ビルドコマンド

# build_gui.ps1 を使用
$env:PATH = "C:\msys64\mingw64\bin;C:\Users\ykihi\.cargo\bin;" + $env:PATH
cargo build --release --features gui --bin collatz-gui

8.3 実行

target\release\collatz-gui.exe

9. パフォーマンス特性

9.1 ベンチマーク（\(n \leq 10^7\), max_steps=500）

\(x\)	時間	nums/s	平均 steps/数
3	0.49s	10,200,000	3.5
5	79s	63,300	179
17	1654s	3,020	456

9.2 速度のスケーリング要因

収束性: \(3n+1\) は全数収束（平均3.5ステップ）、\(x \geq 5\) は発散（max_steps まで実行）
ビット成長: \(x\) が大きいほど1ステップでの数値成長が大きく、BigUint 演算コスト増大
u128 有効範囲: 最初の約 \(128 / \log_2(x/2)\) ステップは u128 で処理、以降 BigUint

9.3 最適化履歴

バージョン	手法	5n+1 (\(n \leq 10^6\)) 速度
v0.1	PairNumber + BigUint 変換/ステップ	46ms/数 (92数/5.65s)
v0.2	BigUint 直接演算 + u128 高速パス	8μs/数 (499,999/4s)
改善倍率		約 5,750倍

10. 既知の制限

\(x-1\) が2の冪でない \(x\) には非対応: \(x=7, 11, 13\) 等は加算段が複数になり、現在の2段構成では処理不可
PairNumber 表現の非効率性: Vec<u8> per bit（8倍メモリオーバーヘッド）。軌道追跡パスでのみ使用
GUI ログビューア: output/ 内の .txt ファイルのみ対応。CSV の直接閲覧は未実装
タイムスタンプ精度: 簡易計算のため閏年未考慮