フィボナッチ素数とは？具体例・素数になる条件とPythonでの調べ方
フィボナッチ素数とは、フィボナッチ数列に現れる数のうち、素数であるものです。
小さい順に並べると、2、3、5、13、89、233、1597……と続きます。例えば13はフィボナッチ数列に含まれ、1と13以外の正の約数を持たないため、フィボナッチ素数です。
ただし、フィボナッチ数がすべて素数になるわけではありません。また、「素数番目のフィボナッチ数なら必ず素数」というわけでもありません。
この記事では、具体例で違いを確認し、最後にPythonでフィボナッチ素数を探します。
目次
フィボナッチ数列と素数の基本
フィボナッチ数列は、直前の2つの数を足して次の数を作る数列です。
この記事では、番号を0から始め、次のように定義します。
- F₀＝0
- F₁＝1
- Fₙ＝Fₙ₋₁＋Fₙ₋₂（n≧2）
実際に並べると、次のようになります。
| 番号n | フィボナッチ数Fₙ | 計算 |
|---|---|---|
| 0 | 0 | 最初に決める値 |
| 1 | 1 | 最初に決める値 |
| 2 | 1 | 0＋1 |
| 3 | 2 | 1＋1 |
| 4 | 3 | 1＋2 |
| 5 | 5 | 2＋3 |
| 6 | 8 | 3＋5 |
| 7 | 13 | 5＋8 |
| 8 | 21 | 8＋13 |
一方、素数は、正の約数が1と自分自身の2つだけである、2以上の整数です。
2、3、5、7、11、13などが該当します。1は正の約数が1つしかないため、素数に含めません。
フィボナッチ素数は、この2つの条件を両方満たす数です。
フィボナッチ素数の具体例
フィボナッチ数列の中から、素数になるものと、ならないものを確認してみましょう。
| 番号n | フィボナッチ数Fₙ | 判定 |
|---|---|---|
| 3 | 2 | 素数 |
| 4 | 3 | 素数 |
| 5 | 5 | 素数 |
| 6 | 8 | 合成数：2×2×2 |
| 7 | 13 | 素数 |
| 8 | 21 | 合成数：3×7 |
| 9 | 34 | 合成数：2×17 |
| 10 | 55 | 合成数：5×11 |
| 11 | 89 | 素数 |
| 13 | 233 | 素数 |
| 17 | 1,597 | 素数 |
| 19 | 4,181 | 合成数：37×113 |
※合成数は、2以上の整数のうち、素数ではない数です。
ここで、番号nと、その位置にある数Fₙは別のものだと意識してください。
例えば、F₇＝13では「7」が番号、「13」がフィボナッチ数です。素数かどうかを調べたいのは、まず値である13の方です。
フィボナッチ数が素数になるための条件
フィボナッチ素数には、次の性質があります。
Fₙが素数なら、nは素数または4です。
これは「そうなることが多い」という傾向ではなく、成り立つ性質です。例外となる番号4では、F₄＝3が素数になります。
なぜ番号にも条件があるのか
背景には、正の整数aがbを割り切るとき、FₐもFᵦを割り切るという性質があります。
例えば、4は8を割り切ります。それに対応して、F₄＝3もF₈＝21を割り切ります。
番号nが4以外の合成数なら、3以上でnより小さい約数aを選べます。このときFₐは、1より大きくFₙより小さい約数になるため、Fₙは素数になりません。
n＝4では、1以外の適切な約数は2ですが、F₂＝1です。そのため、この場合だけはF₄が合成数だとはいえず、実際にF₄＝3は素数になります。
番号が素数でも、値が素数になるとは限らない
注意したいのは、先ほどの性質を逆向きには使えないことです。
19は素数ですが、
となり、フィボナッチ数の方は合成数です。
つまり、「番号が素数か4であること」は候補を絞るための条件であり、その値が素数だと保証する条件ではありません。
Pythonでフィボナッチ素数を探す
実際にプログラムを動かして確認してみましょう。
以下のコードは、F₀からF₃₀までを作り、その中から素数だけを取り出します。Python 3.8以降で動作し、追加ライブラリは不要です。
from math import isqrt
def is_prime(number):
"""2以上の整数が素数かどうかを判定する。"""
if number < 2:
return False
for divisor in range(2, isqrt(number) + 1):
if number % divisor == 0:
return False
return True
def fibonacci_primes(max_index):
"""F_0からF_max_indexまでのフィボナッチ素数を返す。"""
a, b = 0, 1
results = []
for n in range(max_index + 1):
if is_prime(a):
results.append((n, a))
a, b = b, a + b
return results
for n, value in fibonacci_primes(30):
print(f"F_{n} = {value}")
実行方法
- コードを
fibonacci_primes.pyという名前で保存します。 - 保存先のフォルダでターミナルを開きます。
python fibonacci_primes.pyを実行します。
環境によっては、pythonの代わりにpython3を使います。
実行結果は次のとおりです。
この範囲では、9個のフィボナッチ素数が見つかります。値と番号は、整数列データベースOEISの掲載内容とも一致します。
コードの仕組みを理解する
平方根まで割って調べればよい理由
is_primeでは、2から調べる数の平方根まで、割り切れる整数があるかを確認しています。
合成数を2つの整数の積で表すと、少なくとも一方は平方根以下になります。両方が平方根より大きければ、積が元の数より大きくなってしまうからです。
例えば91なら、平方根は約9.54です。2～9を調べる途中で7で割り切れることが分かり、合成数だと判定できます。
isqrtは、平方根の整数部分を正確に求めるPython標準の関数です。浮動小数点の平方根を整数へ変換する方法と違い、整数計算で求められます。
2つの変数で数列を作る
aとbには、隣り合うフィボナッチ数を入れています。
繰り返しの最初では、aがFₙ、bがFₙ₊₁です。aを素数判定した後に、
で、次の組へ進みます。
Pythonでは右側を先に評価するため、更新前のaとbを使って次の値を計算できます。
また、fibonacci_primes(30)の30は、調べる番号の上限です。「素数を30個見つける」という意味ではありません。
大きな番号では処理が重くなる
このコードは、仕組みを学ぶための試し割りによる実装です。
フィボナッチ数は番号が進むと急速に大きくなるため、調べる番号を大幅に増やすと、素数判定に時間がかかります。まずは30程度の範囲で、数列の生成と判定の流れを確認してください。
よくある質問
フィボナッチ素数は無限にありますか？
無限に存在すると予想されていますが、まだ証明されていません。
プログラムで多くの例を見つけることと、無限に存在すると数学的に証明することは別です。
すべての素数はフィボナッチ数列に現れますか？
現れません。
例えば7は素数ですが、フィボナッチ数列は5の次が8なので、7を含みません。フィボナッチ素数は、素数全体の一部です。
フィボナッチ数列の1は素数ですか？
素数ではありません。
数列に含まれるかどうかに関係なく、素数は2以上の整数です。今回のプログラムでも、2未満の数は素数ではないと判定しています。
数学の条件を、プログラムで確かめる
フィボナッチ素数を調べると、数列の規則、素数判定、必要条件と十分条件の違いを一緒に学べます。
特に重要なのは、番号が素数でも、その位置のフィボナッチ数が素数とは限らないという点です。
まずは表で予想し、プログラムで確かめ、なぜその結果になるのかを考えてみてください。短いコードでも、数学の性質とアルゴリズムの関係を具体的に体験できます。
Learning Tools
記事を検索したい方はここから！
記事を検索
関連記事や、今の内容に近いテーマをすぐに検索できます。
例: AI / 情報Ⅰ / Python / 統計 / 資格 / 学習法