Project Euler 問題2（偶数のフィボナッチ数）を解いてみる（続き）

前回は、Project Euler で紹介されている問題2を解いてみました。今回は、別のアイデアでの実装を2つほど紹介します。またフィボナッチ数列に現れる倍数の項についての法則も紹介します。

再掲載　問題2（偶数のフィボナッチ数）

解答例（改善版2）

フィボナッチ数列では、偶数の項は3項毎に現れます。
改善版1では、3項先（と2項先）の値を直接計算しましたが、それであれば、足し算を3回行って、3項先を求めればよいのでは、という方針で実装してみました。

なお、フィボナッチ数列は、問題文のように1と2から始める場合（1, 2, 3, 5, …）と、0と1から始める場合（0, 1, 1, 2, 3, 5, …）と、1と1から始める場合（1, 1, 2, 3, 5, …）で同じ数列となります。
最初の偶数である2をループ文で処理するために、以下のプログラムは1と1から始めています。

#include <stdio.h>

int main(void)
{
	int i1, i2, i3, sum;

	i1 = 1;
	i2 = 1;
	sum = 0; /* no even number */

	i3 = i1 + i2;
	while (i3 <= 4000000) {
		sum += i3;
		i1 = i2 + i3;
		i2 = i3 + i1;
		i3 = i1 + i2;
	}

	printf("Problem002: %d\n", sum);

	return 0;
}

while ループは、偶数分しか繰り返しませんし、条件判断文もありません。また、改善版1と比較すると、ループの繰り返し中は、足し算だけになっています。コードとしてもこちらのほうが読みやすいでしょうか。

解答例（改善版3）

フィボナッチ数列は、以下でした。

　1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, …

偶数だけ取り出してみましょう。

　2, 8, 34, 144, 610, …

以下の法則に気づいたでしょうか。

　34 = 8 × 4 + 2
　144 = 34 × 4 + 8
　610 = 144 × 4 + 34

以下、各項をFn（n：自然数）と書きます。34（F8）、8（F5）、2（F2）について、考えてみましょう。それぞれの項は、前2項の和となります。

　F8 = F7 + F6 =（F6 + F5）+（F5 + F4）
　　　=（F5 + F4）+ F5 + F5 +（F3 + F2）
　　　= 3 × F5 ＋（F4 + F3）+ F2
　　　= 3 × F5 ＋ F5 + F2
　　　= 4 × F5 ＋ F2

この関係は、144（F11）、34（F8）、8（F5）についても同じように成立します。この性質を使った実装です。

#include <stdio.h>

int main(void)
{
	int i1, i2, i3, sum;

	i1 = 2;
	i2 = 8;
	sum = 10; /* 2 + 8 */

	i3 = i1 + 4 * i2;
	i1 = i2;
	i2 = i3;
	while (i3 <= 4000000) {
		sum += i3;
		i3 = i1 + 4 * i2;
		i1 = i2;
		i2 = i3;
	}

	printf("Problem002: %d\n", sum);

	return 0;
}

この例も、while ループは、偶数分しか繰り返しませんし、条件判断文もありません。ただし、上で示した偶数の法則に気づかないと、何をやっているのか分からない（本当に問題が解けているか分からない）側面はあります。

考察

3の倍数となるフィボナッチ数

フィボナッチ数列から、3の倍数を取り出してみましょう。

　1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, …

4項毎に現れます。これは偶然でしょうか。同じ数列を3で割った余りを考えてみましょう。

　1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, …

フィボナッチ数列は、前の2項を加えたものが次の項になりますが、3で割った余りにも同じことが言えます（前の2項の余りを加えると、次の項の余りになります）。
青字（1, 2）のところから同じことが繰り返されます。3の倍数の場合、3の次の21（2 + 1）と次の144（1 + 2）では、余りの加え方が異なります。3の倍数は、偶然ですが繰り返しの中の余りが0になる間隔が同じでした。結果として、3の倍数は4項毎に現れます。

4の倍数となるフィボナッチ数

しつこいですが、フィボナッチ数列から、4の倍数を取り出してみましょう。

　1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, …

同じ数列を4で割った余りを考えてみましょう。

　1, 2, 3, 1, 0, 1, 1, 2, 3, 1, 0, 1, 1, 2, 3,

青字（3, 1）のところから同じことが繰り返されます。つまり4の倍数は6項毎に現れます。上の数列をもう2項計算して正しいことを確認しましょう。

　…, 610, 987, 1597, 2584（=646 × 4）

まとめと一般論

考察したフィボナッチ数列の性質をまとめます。

• 2の倍数は3項毎に現れる。
• 3の倍数は4項毎に現れる。
• 4の倍数は6項毎に現れる。

フィボナッチ数列では、一般的に自然数 n で割った余りを考えると、どこかで同じパターンが循環します。これは、前の2項の余りのパターンが、たかだか n × n 通りしかないため、どこかで同じ組み合わせが現れるためです。

偶数だけのフィボナッチ数列を考えることから、興味深いことが分かりました。

最後に

今回、紹介した2通りの実装は、Project Euler が正解者向けに公開している解説を参考にしました。フィボナッチ数列については、知っているつもりでしたが、3項毎に偶数が現れることは、この問題を解くまで気づきませんでした。いろいろな切り口がある数列のようです。

引き続き、Project Euler の問題を紹介していきます。