n番目のフィボナッチ数が10の倍数かどうかを効率的に判定する方法

ここでは、n番目のフィボナッチ数が10の倍数かどうかを、数列を実際に計算することなく効率的に判定する方法を紹介します。

例として、フィボナッチ数列を {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987} とします。このとき、15番目（0から数えて）の項である 610 は10で割り切れます。つまり、n が15の倍数であれば判定結果は true になります。

素朴なアプローチとその課題

最も単純な方法は、指定された項までフィボナッチ数を順に生成し、その値が10で割り切れるかを確認することです。しかし、この方法は項の位置が大きくなると計算コストが膨大になり、巨大な整数の演算も必要になるため、実用的な解法とは言えません。

規則性に着目した効率的なアプローチ

フィボナッチ数列には、2や5で割り切れる項が一定の周期で現れるという美しい規則性があります。

2の倍数になる項：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987
2で割り切れる項は、3項ごとに出現します。

5の倍数になる項：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987
5で割り切れる項は、5項ごとに出現します。

3と5の最小公倍数（LCM）は15です。したがって、15番目ごとのフィボナッチ数（0番目・15番目・30番目…）は必ず10の倍数になることが分かります。逆に言えば、n が15で割り切れるかどうかを確認するだけで、n番目のフィボナッチ数が10の倍数かどうかを定数時間 O(1) で判定できるのです。

アルゴリズム

fiboDivTen(term)

開始
    もし term が 15 で割り切れるならば
        true を返す
    終了
    false を返す
終了

C++による実装例

#include<iostream>
using namespace std;
bool fiboDivTen(int term) {
    if(term % 15 == 0){
        return true;
    }
    return false;
}
int main() {
    int term = 45;
    if (fiboDivTen(term))
        cout << "Divisible";
    else
        cout << "Not Divisible";
}

出力

Divisible

この例では term = 45 であり、45は15の倍数なので「Divisible（割り切れる）」と出力されます。このように、実際にフィボナッチ数を求めなくても、剰余演算ひとつで瞬時に判定できるのがこの手法の大きな利点です。