一般フィボナッチ数列の周期について(1)

　祖先型の目で眺めたこの惑星は, 十分近づいても赤道と極以外に陸地が無いように見える.しかし周回軌道上でよく目を凝らせばその勘違いが, 青色と海を結びつける先入観に起因するものだと気付く. あるところでは群れをなし, またあるところでは毛羽立ち, 赤道では渦巻く白い雲の下にいくらか隠されながらも滑らかで穏やかな表面を見せるのが海洋だ.その一方で, 皺がよったようにわずかずつ異なる「青色」が縦横に走る領域があることが分かるだろう. 海に見えていた部分の3割は青い植物で覆われた大陸なのだ.

　伝統的な分類で主系列のF型星に属すこの系の太陽は我々の故郷のソルよりいくらか重く,その放つ光はやや明るい. そしてスペクトルのピークは短波長側にずれている. つまり少しだけ青い. 植物が持つクロロフィル――と相似な分子――が, もっともエネルギーに富む波長を選んでいないように見えるのはここでもどうやら同じようだ.

　といっても光合成の担い手が全て青いわけではない. やはり地球同様に植物の上陸が一度だけ起こったこの惑星では,現生の陸生青色植物の光合成色素は数億年間経った今でも高い一様性を保っている. しかし水中に目を転ずれば進化の試行錯誤の跡と多様性を見ることができるだろう. いくつもの系統樹の枝に渡って存在する単細胞の藻類は, この惑星を酸素で改造した祖先と微妙に異なる多様な光合成色素を持ち, 淡水海水に限らずあらゆる水圏で食物連鎖を支えていた. カルシウムの骨格を獲得したある藻類のグループはほとんど黒に近い紺色で, 浅瀬の動物に住処を与え生態系にとって重要な役割を果たしていた.

　我々が出会った緋色藻は, 高緯度地域の湖で赤く小さな体を漂わせる,そんな多くの興味深い藻類の中の1つだった.

[ライブラリ＞数学＞数論＞フィボナッチ数列]

　0,1,1,2,3,5,8,13,……言わずと知れたフィボナッチ数列.少し計算すると15番目の610で初めて最後の桁が0になる.さらに根気よく計算を続けていけば最後の桁の数がある周期を持つことに気付くだろう.と言っても21番目の10946に至ってもまだ一巡りしない.そこで最後の桁の数だけで計算を続けてみよう.

0,1,1,2,3,5,8,3,1,4,5,9,4,3,7,0,7,7,4,1,5,6,1,7,8,5,3,8,1,9,
0,9,9,8,7,5,2,7,9,6,5,1,6,7,3,0,3,3,6,9,5,4,9,3,2,5,7,2,9,1,
0,1,1,…

と60番目で0, 61番目で1が出てきて以降は繰り返されることが分かる.すなわち周期は60である.*1.

　さて, 「最後の桁の数」は我々の手が10本(十進数で)の指を備えている事情から
見えているに過ぎない. 他の自然数*2
に対する剰余の周期も気になるところである.

mod 2 : 0,1,1,0,1,1,…
mod 3 : 0,1,1,2,0,2,2,1,0,1,1,….
mod 4 : 0,1,1,2,3,1,0,1,1,…
mod 5 : 0,1,1,2,3,0,3,3,1,4,0,4,4,3,2,0,2,2,4,1,0,1,1,…

こうなると更に気になるのは0,1以外から始めた場合だ.とりあえず法を素数に限るのが常套手段*3.

　上の列を見ると2,3では全ての組が尽くされているが, mod5で出てきていない組があることに気付く.探すとそれは0が出てこない周期4の列,

1,3,4,2,1,3,…

であることが分かる.これら2つでmod5は尽くされるのだ. ただし0,0,0,…は自明だからこの例に限らず除くとする.

　mod7ではどうか.

● 0, 1, 1, 2, 3, 5, 1, 6, 0, 6, 6, 5, 4, 2, 6, 1, 0, 1, …
● 0, 2, 2, 4, 6, 3, 2, 5, 0, 5, 5, 3, 1, 4, 5, 2, 0, 2, …
● 0, 3, 3, 6, 2, 1, 3, 4, 0, 4, 4, 1, 5, 6, 4, 3, 0, 3, …

これで7*7-1個の2つ組は尽くされた.

　mod11では?

● 0, 1, 1, 2, 3, 5, 8, 2, 10, 1, 0, 1, …
● 0, 2, 2, 4, 6, 10, 5, 4, 9, 2, 0, 2, …
● 0, 3, 3, 6, 9, 4, 2, 6, 8, 3, 0, 3, …
● 0, 4, 4, 8, 1, 9, 10, 8, 7, 4, 0, 4,…
● 0, 5, 5 ,10, 4, 3, 7, 10, 6, 5, 0, 5,…
● 0, 6, 6, 1, 7, 8, 4, 1, 5, 6, 0, 6, …
● 0, 7, 7, 3, 10, 2, 1, 3, 4, 7, 0, 7, …
● 0, 8, 8, 5, 2, 7, 9, 5, 3, 8, 0, 8, …
● 0, 9, 9, 7, 5, 1, 6, 7, 2, 9, 0, 9, …
● 0, 10, 10, 9, 8, 6, 3, 9, 1, 10, 0, 10, …

0の入る場合はこれで全てだ. しかし周期10*10=100組だけしか入っていない.
11*11のマス目に印を付けてみると, 出てこない組が分かる.

● 1, 4, 5, 9, 3, 1, 4, …
● 1, 8, 9, 6, 4, 10, 3, 2, 5, 7, 1, 8, …
● 2, 8, 10, 7, 6, 2, 8, …

周期5+10+5=20組. これで全てだ.

　mod13では

● 0, 1, 1, 2, 3, 5, 8, 0, 8, 8, 3, 11, 1, 12, 0, 12, 12, 11, 10, 8, 5, 0, 5, 5, 10, 2, 12, 1, 0, 1, …
● 0, 2, 2, 4, 6, 10, 3, 0, 3, 3, 6, 9, 2, 11, 0, 11, 11, 9, 7, 3, 10, 0, 10, 10, 7, 4, 11, 2, 0, 2, …
● 0, 4, 4, 8, 12, 7, 6, 0, 6, 6, 12, 5, 4, 9, 0, 9, 9, 5, 1, 6, 7, 0, 7, 7, 1, 8, 9, 4, 0, 4, …

0を含む列は周期28が3つ, ここに入る2つ組は84. 0を含まないものは

● 2, 1, 3, 4, 7, 11, 5, 3, 8, 11, 6, 4, 10, 1, 11, 12, 10, 9, 6, 2, 8, 10, 5, 2, 7, 9, 3, 12, 2, 1, …
● 4, 2, 6, 8, 1, 9, 10, 6, 3, 9, 12, 8, 7, 2, 9, 11, 7, 5, 12, 4, 3, 7, 10, 4, 1, 5, 6, 11, 4, 2, …
● 8, 4, 12, 3, 2, 5, 7, 12, 6, 5, 11, 3, 1, 4, 5, 9, 1, 10, 11, 8, 6, 1, 7, 8, 2, 10, 12, 9, 8, 4, …

周期28が3つ. 0を含むものと同じ形だ.

　観察のため, mod17, 19も続けてみる.

mod17

0を含むもの
●0, 1, 1, 2, 3, 5, 8, 13, 4, 0, 4, 4, 8, 12, 3, 15, 1, 16, 0, 16, 16, 15, 14, 12, 9, 4, 13, 0, 13, 13, 9, 5, 14, 2, 16, 1, …
●0, 2, 2, 4, 6, 10, 16, 9, 8, 0, 8, 8, 16, 7, 6, 13, 2, 15, 0, 15, 15, 13, 11, 7, 1, 8, 9, 0, 9, 9, 1, 10, 11, 4, 15, 2, …
●0, 3, 3, 6, 9, 15, 7, 5, 12, 0, 12, 12, 7, 2, 9, 11, 3, 14, 0, 14, 14, 11, 8, 2, 10, 12, 5, 0, 5, 5, 10, 15, 8, 6, 14, 3, …
●0, 6, 6, 12, 1, 13, 14, 10, 7, 0, 7, 7, 14, 4, 1, 5, 6, 11, 0, 11, 11, 5, 16, 4, 3, 7, 10, 0, 10, 10, 3, 13, 16, 12, 11, 6, …
周期36*4列.

0を含まないもの
●1, 3, 4, 7, 11, 1, 12, 13, 8, 4, 12, 16, 11, 10, 4, 14, 1, 15, 16, 14, 13, 10, 6, 16, 5, 4, 9, 13, 5, 1, 6, 7, 13, 3, 16, 2, …
●1, 4, 5, 9, 14, 6, 3, 9, 12, 4, 16, 3, 2, 5, 7, 12, 2, 14, 16, 13, 12, 8, 3, 11, 14, 8, 5, 13, 1, 14, 15, 12, 10, 5, 15, 3, …
●1, 7, 8, 15, 6, 4, 10, 14, 7, 4, 11, 15, 9, 7, 16, 6, 5, 11, 16, 10, 9, 2, 11, 13, 7, 3, 10, 13, 6, 2, 8, 10, 1, 11, 12, 6, …
●1, 9, 10, 2, 12, 14, 9, 6, 15, 4, 2, 6, 8, 14, 5, 2, 7, 9, 16, 8, 7, 15, 5, 3, 8, 11, 2, 13, 15, 11, 9, 3, 12, 15, 10, 8, …
周期36*4列.

mod19

0を含むもの
●0, 1, 1, 2, 3, 5, 8, 13, 2, 15, 17, 13, 11, 5, 16, 2, 18, 1, …
●0, 2, 2, 4, 6, 10, 16, 7, 4, 11, 15, 7, 3, 10, 13, 4, 17, 2, …
●0, 3, 3, 6, 9, 15, 5, 1, 6, 7, 13, 1, 14, 15, 10, 6, 16, 3, …
●0, 4, 4, 8, 12, 1, 13, 14, 8, 3, 11, 14, 6, 1, 7, 8, 15, 4, …
●0, 5, 5, 10, 15, 6, 2, 8, 10, 18, 9, 8, 17, 6, 4, 10, 14, 5, …
●0, 6, 6, 12, 18, 11, 10, 2, 12, 14, 7, 2, 9, 11, 1, 12, 13, 6, …
●0, 7, 7, 14, 2, 16, 18, 15, 14, 10, 5, 15, 1, 16, 17, 14, 12, 7, …
●0, 8, 8, 16, 5, 2, 7, 9, 16, 6, 3, 9, 12, 2, 14, 16, 11, 8, …
●0, 9, 9, 18, 8, 7, 15, 3, 18, 2, 1, 3, 4, 7, 11, 18, 10, 9, …
●0, 10, 10, 1, 11, 12, 4, 16, 1, 17, 18, 16, 15, 12, 8, 1, 9, 10, …
●0, 11, 11, 3, 14, 17, 12, 10, 3, 13, 16, 10, 7, 17, 5, 3, 8, 11, …
●0, 12, 12, 5, 17, 3, 1, 4, 5, 9, 14, 4, 18, 3, 2, 5, 7, 12, …
●0, 13, 13, 7, 1, 8, 9, 17, 7, 5, 12, 17, 10, 8, 18, 7, 6, 13, …
●0, 14, 14, 9, 4, 13, 17, 11, 9, 1, 10, 11, 2, 13, 15, 9, 5, 14, …
●0, 15, 15, 11, 7, 18, 6, 5, 11, 16, 8, 5, 13, 18, 12, 11, 4, 15, …
●0, 16, 16, 13, 10, 4, 14, 18, 13, 12, 6, 18, 5, 4, 9, 13, 3, 16, …
●0, 17, 17, 15, 13, 9, 3, 12, 15, 8, 4, 12, 16, 9, 6, 15, 2, 17, …
●0, 18, 18, 17, 16, 14, 11, 6, 17, 4, 2, 6, 8, 14, 3, 17, 1, 18, …
周期18*18列

0を含まないもの
●1, 5, 6, 11, 17, 9, 7, 16, 4, …
●1, 15, 16, 12, 9, 2, 11, 13, 5, 18, 4, 3, 7, 10, 17, 8, 6, 14, …
●2, 10, 12, 3, 15, 18, 14, 13, 8, …
周期9が2つ, 周期18が1つ.

こうして課題が見えてきた.
- 周期を決めるのは何か?
- 0が初めて現れるのはいつか?
- 0を含まない系列があるのはいかなる場合か?
- 0を含むとすれば循環節中にいくつ含むか?
- 他より短い周期の系列が生じるのはいつか?

　(0,1)から始まる系列において0が初めて出てくる番号は出現点(エントリーポイント)と呼ばれ, 周期と同様に重要である.また, 0を含む系列が1つ存在すれば, 各成分に対してある数をかけることで他の系列が全て得られることはほとんど明らかだろう.このことを踏まえ, 愚直にp*pのマス目にチェックを入れながら各系列について計算する方法で上の
項目についてもっと調べてみよう.

法p	0を含む系列	周期	出現点	0の数	0を含まない系列
2	1	3	3	1	0
3	1	8	4	2	0
5	1	20	5	4	1
7	3	16	8	2	0
11	10	10	10	1	2+1
13	3	28	7	4	3
17	4	36	9	4	4
19	18	18	18	1	2+1
23	11	48	24	2	0
29	28	14	14	1	32+2
31	30	30	30	1	2+1
37	9	76	19	4	9
41	20	40	20	2	22
43	21	88	44	2	0
47	23	32	16	2	46
53	13	108	27	4	13
59	58	58	58	1	2+1
61	15	60	15	4	47
67	33	136	68	2	0
71	70	70	70	1	2+1
73	18	148	37	4	18
79	78	78	78	1	2+1
83	41	168	84	2	0
89	22	44	11	4	158
97	24	196	49	4	24

　「0を含まない系列」の項の"+1","+2"は短い周期のものがその数だけ現れていることを示す. 表には書いていないが,その長さは他の系列のちょうど半分になっている.つまり短い系列はそれほどたくさん現れずどうやらその長さは他の半分らしい.

　……ただしp=5の場合は他とは異なる. 上で見たように, 0を4つ含む周期20の系列と1,3,4,2,…の周期4の系列が現れる. これは端的に5という数がフィボナッチ数において特殊な役割を果たしていることを表している.

　今から示していくのは, 実は出現点さえ分かればこの表の他の項目は埋められるということだ. p*pのマス目を埋めていく必要はないのだ.

　そのためにフィボナッチ数について定義や重要ないくつかの命題をまとめよう.

定義1.1 フィボナッチ数列{F[n]}とは,

によって定まる再帰数列である.

　この定義では添え字は非負整数に限っているが負数番への拡張は容易だ.単にn<0に対してはF[n]=F[n+2]-F[n+1]とすればいい. そして単に偶数番に負号が付くだけであることもすぐに分かる.一応命題として述べておこう.

命題1.1　n>0に対して

　しかし初項が(0,1)だけではあまりに窮屈だ.同じ形の再帰数列を, 初項を一般の整数の組にも拡げて「一般フィボナッチ数列」とまとめて呼ぼう.

定義1.2 初項が(a,b)∈Z^2の一般フィボナッチ数列{G[n]}を

によって定める.

　後に分かることだが, a=2, b=1の場合はフィボナッチ数列と「対」になると言える重要な数列である.これをリュカ数列*4と呼ぶ.

定義1.3
リュカ数列[L[n]}とは

によって定まる数列である.

最初の数項は2,1,3,4,7,11,18,29,…となる.

　さて, 一般フィボナッチ数列も何項か計算してみればすぐにその規則に気付くだろう.

a, b, a+b, a+2b, 2a+3b, 3a+5b, …

係数にフィボナッチ数が現れている. これを命題として述べよう.

命題1.2　初項(a,b)の一般フィボナッチ数列{G[n]}に対して

証明は略すが数学的帰納法からすぐに示せる.

　より一般的な形として

命題1.3　

さらにここから系として

命題1.4

も簡単に示される.

　この関係式から感じられるように, フィボナッチ数列は行列を使うと見通しが良くなる.線型回帰数列であるから当然のことではある.簡単のためこの2つ組を「進める」行列に記号Fを当てておき以後断りなく使う.

命題1.5
行列Φ,横ベクトルg[n]を以下のように定めると次の関係式が成り立つ.

さらに行列G[n]を定めると,　

特に,

ベクトルに対して後ろから行列を書ける形式にしたのは横ベクトルで使いたいことが理由で, 特に深い意味は無い.

行列式を比較することから次の命題が得られる.

命題1.6

3番目の等式はシムソンの等式と呼ばれている*5.

　この行列Fの対角化と累乗により次の有名な等式、ビネーの公式*6*7が得られる.

命題1.7(ビネーの公式)

λ^2-λ-1の2つの解をα,βとすると,

リュカ数列に対しても同様の等式が得られる.

命題1.8

　今でこそ当たり前の公式だが, やはり整数しか出てこない数列の一般項を無理数のべき乗の線形和で表せてしまうというのは驚きである. これが整数になることはもちろん帰納法からすぐに示せるが, 有理数であることなら「直接」示せるだろう. αとβのべき乗を足すと√5が「消える」ことを言えばよいのだ. そのために二項定理を使う.

　これはカタランの公式と呼ばれるものである.

命題1.9(カタランの公式)

　リュカ数についても同様の式が成り立つが, 特に直接用いることはないため省略.

　ここまでで以後用いるフィボナッチ数についての一般的な定義と命題については一通り述べ終えた. この準備を踏まえ, 次の記事から整除性と周期について述べる.

*1:この観察はラグランジュによるものとしてコクセター『幾何学入門』(ちくま学芸文庫)で紹介されている……もっと前から知られていそうな気はするが

*2:数論の話になるため自然数に0を含めない

*3:法10を導入にしておきながら…

*4:一般の二階線形回帰数列にも同じくフランスの数学者エドゥアール・リュカ(1842-1891)の名前が冠せられていたりするがこの名前で呼ぶ

*5:それ以前にカッシーニ、カタラン達も発見していたようである.

*6:J.P.M.ビネー(仏 1786-1856). この名で呼ばれることが多いこの公式は, しかしビネーによって「再発見」されたものに過ぎないことが今では知られているようだ. 約1世紀前にオイラー, ダニエル・ベルヌーイ, ド・モアブル達が既に得ていたらしい. このような発見者と名称の不一致は歴史上しばしば見られるが(誰が最初に言い出してどうやって広まるのだろう?), ここでは一応ビネーの公式の名で呼ぶことにする.

*7:多分発見当時は行列の対角化自体をしたわけではないと思う.