フィボナッチ数列におけるn番目の倍数の位置を求めるJavaプログラム

フィボナッチ数列の中である整数の「n番目の倍数」が何番目に現れるのかを求めたい場合、数列の数学的な性質を利用すると効率的に実装できます。この記事では、その処理を行うJavaプログラムのサンプルコードと、その仕組みについて詳しく解説します。

サンプルコード

public class Demo {
   public static int position(int pos, int num) {
      long val_1 = 0, val_2 = 1, val_3;
      int i = 2;
      while (i != 0) {
         val_3 = val_1 + val_2;
         val_1 = val_2;
         val_2 = val_3;
         if (val_2 % pos == 0) {
            return num * i;
         }
         i++;
      }
      return 0;
   }

   public static void main(String[] args) {
      int n = 10;
      int k = 9;
      System.out.print("フィボナッチ数列における9の10番目の倍数の位置は ");
      System.out.println(position(k, n));
   }
}

実行結果

フィボナッチ数列における9の10番目の倍数の位置は 120

プログラムの解説

Demo クラスには、フィボナッチ数を順に生成しながら目的の位置を計算する position メソッドが定義されています。main メソッド内では、倍数を調べる対象の数（この例では9）と、何番目の倍数を求めるか（この例では10番目）を変数として定義し、それらを引数としてメソッドを呼び出します。最後に、得られた結果をコンソールに出力します。

アルゴリズムのポイント

• 変数 val_1 と val_2 を使って、フィボナッチ数列を先頭から順に1項ずつ生成していきます。
• 生成したフィボナッチ数 val_2 が pos（この例では9）で割り切れた時点で、その項の位置 i を記録します。
• フィボナッチ数列には「ある数kで割り切れる項は、最初に現れた位置z(k)の倍数の位置に必ず現れる」という重要な性質があります。そのため、最初に割り切れた位置さえ分かれば、n番目の倍数の位置は「num × i」という単純な掛け算で求められます。
• フィボナッチ数は増加が非常に速いため、値の保持には long 型を使用し、オーバーフローをできるだけ回避しています。

実行結果が「120」になる理由

この例では、9で初めて割り切れるフィボナッチ数は第12項の F(12) = 144 です。以降も、9の倍数に該当する項は第12項、第24項、第36項…と12の倍数の位置に現れます。したがって、10番目の倍数の位置は「12 × 10 ＝ 120」と計算され、これが出力結果になります。

このように、全ての項を個別に確認する必要はなく、最初に条件を満たす位置を見つけるだけで答えを導き出せるのが、このアルゴリズムの大きな利点です。