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

本記事では、以下の問題文に対する解決策について詳しく学んでいきます。

問題の定義

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

ご存知のとおり、n番目のフィボナッチ数は「直前の2つのフィボナッチ数の和」として定義されます。しかし、この漸化式以外にも、フィボナッチ数には興味深い数学的な性質が存在します。

フィボナッチ数の判定に使える重要な性質

ある数 n がフィボナッチ数であるのは、次の条件が成り立つ場合、かつその場合に限られます。

• 5×n² + 4 が完全平方数である
• または 5×n² − 4 が完全平方数である

つまり、上記のどちらか一方（または両方）が完全平方数になれば、その数は必ずフィボナッチ数だということです。この性質を利用することで、実際にフィボナッチ数列を生成しなくても、効率よく判定を行うことができます。

Pythonでの実装例

それでは、この性質を使った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 a not Fibonacci Number")

実行結果

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

実行結果から、1〜10の中でフィボナッチ数は「1, 2, 3, 5, 8」であり、「4, 6, 7, 9, 10」はフィボナッチ数ではないことが正しく判定されているのが分かります。

コードのポイント解説

• isPerfectSquare 関数：math.sqrt() で平方根を求め、整数化した値を再び2乗して元の数と一致するか確認することで、完全平方数かどうかを判定します。
• isFibonacci 関数：「5n²+4」または「5n²−4」が完全平方数であるかを論理和（or）でチェックし、どちらかが真であればフィボナッチ数と判定します。

すべての関数と変数はグローバルフレーム内で宣言されており、プログラム全体がシンプルで読みやすい構造になっています。

まとめ

本記事では、「5n²+4 または 5n²−4 が完全平方数ならばフィボナッチ数」という数学的性質を利用して、与えられた数がフィボナッチ数かどうかを判定するPythonプログラムを紹介しました。この手法はフィボナッチ数列を順番に生成する必要がないため、単一の数値に対して高速かつ効率的に判定できるのが大きなメリットです。