フィボナッチ数列の剰余
フィボナッチ数列
\[f(1)=1,\quad f(2)=1,\quad f(n+2)=f(n+1)+f(n)\]
の各項を任意の自然数 $a$ で割った余りを並べた数列を
\[g(n)=f(n)\ \mathrm{mod}\ a\]
と定義すると、$g(n)$ は周期をもつ数列になることが知られています。$a=3$ のときは、$g(n)$ は
\[1,\ 1,\ 2,\ 0,\ 2,\ 2,\ 1,\ 0\]
を繰り返す周期 $8$ の数列になります。各点をグラフにプロットしてみると次のようになります。
$a=5,\ a=7$ のときは、それぞれ周期 $20,\ 16$ の数列となります。
剰余を足して作る数列
上記の数列を拡張して、前項と前々項の剰余を足し合わせて数列を作ってみます。すなわち、$a,\ b$ を任意の自然数として
\[f(n+2)=[f(n+1)\ \mathrm{mod}\ a]+[f(n)\ \mathrm{mod}\ b]\]
というような数列を定義してみます。$a=5,\ b=11$ としてグラフを描いてみると次のようになります。
初期値の近くを除けば、この数列もやはり周期性をもちます。
$a=11,\ b=13$ を選ぶと、より単調な周期数列になります。
$a,\ b$ の選び方によって色々な周期数列が現れるので、皆さんも Excel で試してみてください。
