collatz-m4m6 Tool Specification Report

Version: 0.2.0  |  Date: 2026-02-07  |  Language: Rust (edition 2021)

1. Overview

A scan and analysis tool based on the m4/m6 pair predicate decomposition of the Collatz-type map \(T(n) = (xn+1)/2^d\). This is an implementation of Algorithm 7.1 from the paper "Pair Predicate Decomposition of the Collatz-type Map \((xn+1)/2^d\) and Structural Closure of \(3n+1\)," providing the following features.

• Single-step scan for any \(xn+1\)-type map (where \(x-1\) is a power of 2)
• Trajectory tracking (recording all steps until reaching 1)
• Range verification (parallel verification of large numbers using the stopping time method)
• Aggregation and visualization of GPK (Generate/Propagate/Kill) statistics
• Interactive operation via GUI

2. Supported Parameters

Constraint: \(x \geq 3\) and \(x-1\) must be a power of 2.

3. Architecture

3.1 Module Structure

src/
├── lib.rs            # Crate root (public API definitions)
├── main.rs           # CLI entry point
├── gui.rs            # GUI entry point (egui)
├── pair_number.rs    # PairNumber type (m4/m6 bit-pair representation)
├── reference.rs      # Reference patterns (implementation of Table 3.1)
├── scan.rs           # Single-step scan (including GPK classification)
├── postprocess.rs    # Postprocessing (MSB trimming, trailing zero removal, re-pairing)
├── trajectory.rs     # Trajectory tracking / stopping time calculation
└── verify.rs         # Range parallel verification (rayon)

3.2 Data Flow

Input n (BigUint)
    │
    ├─ [Trajectory tracking path] ─── PairNumber conversion → scan::collatz_step → postprocess → record
    │                     (retains m4/m6, GPK sequence, d for each step)
    │
    └─ [Stopping time path] ─── u128 direct arithmetic → BigUint fallback
                          (fast arithmetic without going through PairNumber; GPK computed via bit extraction)

3.3 Dual-Path Design

4. Stopping Time Fast Path

4.1 stopping_time_u64_fast

Optimized path for u64 input.

Phase 1: u128 Arithmetic

• Compute current * x + 1 in u128
• Obtain \(d\) via trailing_zeros(), then right-shift
• GPK is classified directly from bits of the u128 value
• Overflow threshold: (u128::MAX - 1) / x

Phase 2: BigUint Fallback

• Automatic transition upon u128 overflow
• In-place arithmetic via BigUint::*=, +=, >>=
• GPK extracted from bits via to_bytes_le()

4.2 stopping_time_with_gpk

Generic path for BigUint input. Same logic as Phase 2.

4.3 Safety Limits

5. GPK Statistics

5.1 Classification Rules

For each pair position \(i\), from the 4 bits \((p_r, q_r, p_l, q_l)\) based on the reference pattern:

m6 stage: g_mid = p_r & q_r,  p_mid = p_r ^ q_r
m4 stage: g_out = p_l & q_l,  p_out = p_l ^ q_l
Serial composition: G_i = g_out | (p_out & g_mid)
          P_i = p_out & p_mid
          K_i = otherwise

5.2 Carry Chain Length

Records the maximum length of chains starting from the initial carry \(c=1\) and chains after regeneration by G. Aggregated as a histogram (distance 0–127).

5.3 Measured GPK Distribution (\(n \leq 10^7\), max_steps=500)

6. GUI Specification

6.1 Configuration

• Framework: egui (eframe 0.29) + egui_plot 0.29
• Japanese font: Yu Gothic / MS Gothic / Meiryo (auto-detected)
• Window size: 900 × 700

6.2 Top Panel

6.3 Single Analysis Tab

• Single-step execution: Performs one \((xn+1)/2^d\) operation on \(n\). Displays \(n'\), \(d\), GPK sequence, and carry chain length
• Trajectory tracking: Iterates until reaching 1 (or max_steps/bit-length limit). Runs on a background thread
  • Cancellable (stop button)
  • Progress display (step count, digit count) updated every 200ms
  • Result: step count, \(\Sigma d\), maximum digit count, GPK statistics, first 100 steps of trajectory
  • CSV + summary TXT saved automatically

6.4 Range Analysis Tab

• Range specification: Verifies all odd numbers from start value–end value
• Parallel processing: Automatic parallelization via rayon (u64 range is divided into chunks)
• Progress bar: Updated every 100 numbers, displaying nums/s
• Cancellable
• Results: Number verified, convergence determination, maximum stopping time, GPK statistics, GPK distribution graph, carry chain length graph
• Summary TXT saved automatically

6.5 Analysis Tab

• Displays a list of log files in the output/ directory
• Selecting a file re-displays parameters, GPK statistics, and graphs
• Automatically parses the log file format

7. Output Files

7.1 Save Location

The output/ folder in the same directory as the exe (created automatically).

7.2 File Naming Convention

gui_trace_{x}n1_{n}[_stopped]_{timestamp}.txt     # Trajectory tracking summary
gui_trace_{x}n1_{n}.csv                            # Trajectory tracking CSV
gui_verify_{x}n1_{start}-{end}[_stopped]_{timestamp}.txt  # Range verification summary

7.3 Summary File Format

# 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 Format (Trajectory Tracking)

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. Build

8.1 Prerequisites

• Rust toolchain (stable)
• MSYS2 MinGW64 (on Windows, native dependency for egui)

8.2 Build Commands

# Use 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 Execution

target\release\collatz-gui.exe

9. Performance Characteristics

9.1 Benchmark (\(n \leq 10^7\), max_steps=500)

9.2 Scaling Factors for Speed

1. Convergence: \(3n+1\) converges for all numbers (average 3.5 steps); \(x \geq 5\) diverges (runs up to max_steps)
2. Bit growth: Larger \(x\) causes greater numerical growth per step, increasing BigUint arithmetic cost
3. u128 effective range: The first approximately \(128 / \log_2(x/2)\) steps are processed in u128; thereafter BigUint

9.3 Optimization History

10. Known Limitations

1. Values of \(x\) where \(x-1\) is not a power of 2 are unsupported: \(x=7, 11, 13\), etc. require multiple addition stages and cannot be handled by the current two-stage structure
2. Inefficiency of PairNumber representation: Vec<u8> per bit (8x memory overhead). Used only in the trajectory tracking path
3. GUI log viewer: Only supports .txt files in output/. Direct viewing of CSV files is not yet implemented
4. Timestamp precision: Simplified calculation that does not account for leap years