Javaで数値がフィボナッチ数かどうかを判定する方法｜完全平方数を使ったチェックプログラム

ある整数がフィボナッチ数（0, 1, 1, 2, 3, 5, 8, 13, 21…と続く数列に含まれる数）であるかどうかは、実際に数列を生成しなくても、数学的な性質を利用することで効率的に判定できます。

判定の原理：完全平方数の性質

有名な定理によると、n がフィボナッチ数であるのは、「5n² + 4」または「5n² − 4」のどちらか一方が完全平方数になる場合、かつその場合に限ることが証明されています。これを利用すると、O(1) に近い計算量でフィボナッチ数かどうかをチェックできます。

フィボナッチ数判定のJavaプログラム

以下が、与えられた数値がフィボナッチ数かどうかをチェックするJavaプログラムの例です。

サンプルコード

public class Demo{
   static boolean perfect_square_check(int val){
      int s = (int) Math.sqrt(val);
      return (s*s == val);
   }
   static boolean fibonacci_num_check(int n){
      return perfect_square_check(5*n*n + 4) || perfect_square_check(5*n*n - 4);
   }
   public static void main(String[] args){
      for (int i = 6; i <= 17; i++)
      System.out.println(fibonacci_num_check(i) ? i + " is a Fibonacci number" :
      i + " is a not 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
11 is a not Fibonacci number
12 is a not Fibonacci number
13 is a Fibonacci number
14 is a not Fibonacci number
15 is a not Fibonacci number
16 is a not Fibonacci number
17 is a not Fibonacci number

プログラムの仕組み

Demo クラスには、整数値を引数として受け取る静的メソッド perfect_square_check() が定義されています。このメソッドは、渡された値の平方根を Math.sqrt() で求めて変数 s に代入し、「s × s」が元の値と一致するかどうかを返します。一致すれば、その数は完全平方数であると判断できます。

次に、もう一つの静的メソッド fibonacci_num_check() が定義されており、内部で先ほどの perfect_square_check() を呼び出しています。具体的には、5n² + 4 と 5n² − 4 のいずれかが完全平方数であれば true を返すことで、フィボナッチ数の判定を行います。

そして main メソッドでは、開始値の 6 から終了値の 17 までの整数を順番にループ処理し、それぞれの数値がフィボナッチ数であるかどうかを判定して、結果に応じたメッセージを出力します。

実行結果を見ると、範囲内でフィボナッチ数に該当するのは 8 と 13 のみであり、それ以外の数値については「フィボナッチ数ではない」と正しく判定されていることがわかります。