ちょっと気になったのでフィボナッチ数で素数なものをプログラミングで求めてみた。
フィボナッチ数とは、フィボナッチ数列の項となりうる数。
素数は、1と自分自身の2つの約数しか持たない自然数。
２つを同時に満たす数をフィボナッチ素数という。
フィボナッチ数列は、
F1＝1
F2＝1
Fn＝Fn－2＋Fn－1
というように二項間漸化式として定義されていて、
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
といったように無限に続く。
素数は、
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, …
といったように無限に存在する。
ということで、フィボナッチ素数は、
2, 3, 5, 13, 89, 233, 1597, 28657, 514229, 433494437, 2971215073, 99194853094755497
といったように64ビット正整数の範囲で見つけることが出来た。
こうやって並べてしまうと情報が少ないので、フィボナッチ数列の添字と紐づけてみると、
F3＝2
F4＝3
F5＝5
F7＝13
F11＝89
F13＝233
F17＝1597
F23＝28657
F29＝514229
F43＝433494437
F47＝2971215073
F83＝99194853094755497
ということになる。
F4以外の添字が、すべて素数なんですよね。
なんか不思議ですよね。
添字nが素数ならば、Fnは素数になるとは限らないが、
n＝4を除くFnが素数ならば、nは素数
ということは解っているようです。
ただし、フィボナッチ素数は無限に存在するかは未解決のようです。
さて、現時点で解っている最大のフィボナッチ素数はというと、F81839ということらしい。
フィボナッチ数列は、数列を愚直に実行すれば値は求まるのだが、一般項を求めることが出来る。
ベネの公式
| Fn＝ |
1
√5 |
⎧ ⎨ ⎩ |
⎛ ⎝ |
1＋√5
2 |
⎞ ⎠ |
n |
－ | ⎛ ⎝ |
1－√5
2 |
⎞ ⎠ |
n |
⎫ ⎬ ⎭ |
F81839を求めてみたくなってしまったのだ。
多倍長電卓LMを使って、17103桁の整数であることは解っていたので、2万桁を用意して求めてみた。
末尾が0になってしまった。
81839乗しなければならないので、√5の有効桁数が足りなかったのだろうか。
桁数は5万桁まで増やしたが、それでも足りないのか、この方法を一旦断念。
高々81839番目のフィボナッチ数ということで、地道に計算してみました。
末尾が0ではなくなったので、ほっとしました。
後から解ったことなのだが、print文で%dで表示していたこと原因で、%fで表示したら解消されました。
LMは型宣言するわけじゃないので、おそらくそういうところの話しなんだろう。
ではでは