Pythonで与えられた数値がフィボナッチ数かどうかを判定する方法

本記事では、与えられた数値がフィボナッチ数であるかどうかを判定する問題の解決策について解説します。

問題の定義

ある数値 n が与えられたとき、その数値がフィボナッチ数であるかどうかを判定します。

第 n 項のフィボナッチ数は、直前の2つのフィボナッチ数の和として定義されることは広く知られています。しかし、フィボナッチ数列には漸化式以外にも興味深い数学的性質があります。

フィボナッチ数の判定条件

ある数値 n がフィボナッチ数であるのは、「5×n² + 4」または「5×n² − 4」のいずれかが完全平方数であるとき、かつそのときに限る

この性質を利用すれば、フィボナッチ数列を実際に生成しなくても、数値がフィボナッチ数かどうかを高速に判定できます。

Pythonでの実装例

import math

# xが完全平方数かどうかを判定する
def isPerfectSquare(x):
    s = int(math.sqrt(x))
    return s * s == x

# nがフィボナッチ数かどうかを判定する
def isFibonacci(n):
    # 5*n*n + 4 または 5*n*n - 4 のどちらか（または両方）が完全平方数ならTrue
    return isPerfectSquare(5*n*n + 4) or isPerfectSquare(5*n*n - 4)

for i in range(1, 11):
    if isFibonacci(i) == True:
        print(i, "is a Fibonacci Number")
    else:
        print(i, "is not a Fibonacci Number")

コードの解説

• isPerfectSquare(x)：引数 x の平方根を整数化して2乗し、元の値と一致するかを確認することで、x が完全平方数かどうかを判定します。
• isFibonacci(n)：上記の数学的性質に基づき、「5×n² + 4」または「5×n² − 4」のいずれかが完全平方数であれば True を返します。

実行結果

1 is a Fibonacci Number
2 is a Fibonacci Number
3 is a Fibonacci Number
4 is not a Fibonacci Number
5 is a Fibonacci Number
6 is not a Fibonacci Number
7 is not a Fibonacci Number
8 is a Fibonacci Number
9 is not a Fibonacci Number
10 is not a Fibonacci Number

1〜10 のうち、1・2・3・5・8 がフィボナッチ数として正しく判定されていることがわかります。

すべての関数と変数は、下図のようにグローバルフレーム内で宣言されます。

まとめ

本記事では、「5×n² + 4」または「5×n² − 4」が完全平方数かどうかを調べることで、与えられた数値がフィボナッチ数かどうかを効率的に判定する方法を学びました。この手法は、フィボナッチ数列を順に生成して照合する方法よりもシンプルで高速なのが大きな魅力です。