【Python】フィボナッチ数列におけるkのn番目の倍数の位置を求める方法

この記事では、「フィボナッチ数列の中に現れるある数の倍数」をテーマに、Pythonでの解法をサンプルコードとともにわかりやすく解説します。

問題の概要

整数 k と n が与えられたとき、フィボナッチ数列の中で k の n 番目の倍数が何番目の項として現れるかを求めます。

例えば「k = 4 の 5 番目の倍数」なら、フィボナッチ数列を順にたどりながら 4 の倍数になっている項を探し、そのうち 5 番目に該当する項の位置を出力します。

解法のポイント

フィボナッチ数列を k で割った余りには周期性があるため、k の倍数となる項は等間隔で出現します。最初に k の倍数になった項の位置を i とすると、その後の倍数は i の整数倍の位置（i, 2i, 3i, …）に現れます。

この性質を利用すると、次の手順で答えが求まります。

1. フィボナッチ数列の項を順に生成する。
2. 初めて k で割り切れた項の位置を i として記録する。
3. 答えは n × i となるので、その値を返す。

サンプルコード

# kのn番目の倍数の位置を求める関数
def find(k, n):
    f1 = 0   # 前の項
    f2 = 1   # 現在の項
    i = 2    # 現在の項の位置
    # フィボナッチ数列を順に生成
    while True:
        f3 = f1 + f2
        f1 = f2
        f2 = f3
        # kの倍数を見つけたら位置を返す
        if f2 % k == 0:
            return n * i
        i += 1

# 求めたい倍数の番号
n = 5
# 対象となる数
k = 4
print("フィボナッチ数列におけるkのn番目の倍数の位置:", find(k, n))

実行結果

フィボナッチ数列におけるkのn番目の倍数の位置: 30

コードの解説

変数と関数はすべてグローバルスコープで定義されています。処理の流れは以下の通りです。

• f1・f2：フィボナッチ数列の計算に使う変数で、初期値はそれぞれ 0 と 1。
• i：現在注目している項の位置。初期値は 2。
• ループの中で新しい項 f3 = f1 + f2 を計算し、f1 と f2 を入れ替えながら数列を伸ばしていきます。
• f2 % k == 0 が成立した瞬間に、初めて k の倍数となった項の位置 i が確定するので、n × i を返り値とします。

今回の例では、k = 4 のとき最初に 4 の倍数になるのは第 6 項の 8 です。したがって 5 番目の倍数の位置は 5 × 6 = 30 となり、実際に第 30 項の値 832040 は 4 で割り切れることが確認できます。

まとめ

この記事では、フィボナッチ数列における k の n 番目の倍数の位置を Python で求める方法を紹介しました。「k の倍数となる項は等間隔で現れる」というフィボナッチ数列の性質を活かすことで、無駄なく効率的に答えを導き出せます。ぜひご自身の環境でもコードを実行してみてください。