【Project Euler】Problem 25: 1000桁のフィボナッチ数

• 本記事はProjectEulerの「100番以下の問題の説明は記載可能」という規定に基づいて回答のヒントが書かれていますので、自分である程度考えてみてから読まれることをお勧めします。

問題 25：1000桁のフィボナッチ数

原文 Problem 25: 1000-digit Fibonacci number

問題の要約：フィボナッチ数が1000桁を超えるのは何番目か求めよ

素直にインプリですると「Problem 2: 偶数のフィボナッチ数」で作成したフィボナッチ数Generator関数fibgenを使って$10^{1000-1}$を超えるまでループします。

import itertools
fib = fibgen()
for i in itertools.count(1):
  f = next(fib)
  if f > 10**(1000-1): break
print(f"Answer: {i}")
# Answer: 4782

これでも十分早いのですが、余りにも大きい数を扱っているのと、ただループするだけでちょっと脳がないのでちょっと工夫します。

このような大きな数を扱うときには対数のlogを使うのが常套手段ですね。

フィボナッチ数(Wikipedia)によると一般項は、

\begin{align}
&F_n = \frac{1}{\sqrt{5}}\{(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n\} \\
&ですが右辺の第2項はnが大きくなると無視できるので、\\
&F_n \simeq \frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^n>10^{1000-1} \\
&この両辺のlog10を取って移項すると、\\
&n > \frac{1000-1+log_{10}(\sqrt{5})}{log_{10}(\frac{(1+\sqrt(5))}{2})}　
\\
&となります。
\end{align}

これをプログラムにすると一発で答えが求まります。

from math import sqrt, log10, ceil

print(ceil((1000-1+log10(sqrt(5)))/log10(((1+sqrt(5))/2))))

フィボナッチ数の指数表記

【例題】1000番目のフィボナッチ数を仮数部の小数部3桁の指数表記であらわせ

このlogを使う考え方を使うと指数表記にすることができます。

\begin{align}
&LF = log_{10}F_n = log_{10}(\frac{1+\sqrt 5}{2})-log_{10}(\sqrt{5})\\
&仮数部　= 10^{LF-int(LF)} \\
&指数部　= int(LF)
\end{align}

これをコードにすると以下になり、答えは 4.347e208となります。

import math

def fibfloat(n, d):
  logfn = n*math.log10((1+5**(0.5))/2.0) - math.log10(5**(0.5))
  logm = logfn-int(logfn)
  return f"{10**(logm):.0{d}f}e{int(logfn)}"

for n in [10**2, 10**3, 10**4, 10**8]:
  print(n, fibfloat(n, 3))
# 100 3.542e20
# 1000 4.347e208
# 10000 3.364e2089
# 100000000 4.737e20898763

（開発環境：Google Colab）