Pythonで指定した数値がフィボナッチ数かどうかを判定する方法

フィボナッチ数とは

ある数値 n が与えられたとき、その数がフィボナッチ数列に含まれているかどうかを判定します。フィボナッチ数列は、f(0) = 0、f(1) = 1 を初期値とし、i ≥ 2 の各項について f(i) = f(i-1) + f(i-2) という漸化式で定義される数列です。

具体的には、数列は 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... のように続きます。たとえば入力が n = 13 の場合、13 はフィボナッチ数列に含まれるため、出力は True になります。

解法のアプローチ:黄金比を利用した判定

この問題は、黄金比(φ ≈ 1.618...)の性質を利用することで効率的に解けます。フィボナッチ数と黄金比の間には深い数学的な関係があり、n がフィボナッチ数である場合、φ × n はほぼ整数に近い値になります。この性質を利用して、以下の手順で判定を行います。

• phi := 0.5 + 0.5 × √5.0(黄金比 φ を計算)
• a := phi × n(n に黄金比を掛ける)
• n が 0 である、または a が整数(丸めた値との差が十分小さい)場合に True を返す

実装例

以下にPythonでの実装例を示します。

from math import sqrt

def solve(n):
    phi = 0.5 + 0.5 * 5.0**0.5
    a = phi * n
    return n == 0 or abs(round(a) - a) < 1.0 / n

n = 13
print(solve(n))

入力

13

出力

True

コードのポイント

このアルゴリズムの計算量は O(1) であり、数列を順番に生成しながら比較する方法(O(n))よりもはるかに高速です。ただし、浮動小数点演算には精度の限界があるため、非常に大きな数値を扱う場合は誤差に注意が必要です。このコードでは許容誤差を 1.0 / n として設定することで、大きな数に対しても判定精度を保っています。