Project Euler Problem 25 - 1000桁のフィボナッチ数

Problem 25 - Project Euler

フィボナッチ数が1000桁に達するのは何項目か。

以下解答。

gmpパッケージのbigzクラスを使えばbruteforceしても0.3秒以下。

library(gmp)

n = as.bigz(1)
m = as.bigz(1)
cnt = 2
limit = 1000
while(nchar(as.character(as.bigz(m))) < limit){
  tmp = m
  m = n + m
  n = tmp
  cnt = cnt + 1
}
cnt

ところで、フィボナッチ数の一般項はよく知られているように\phi = \frac{1 + \sqrt{5}}{2}として、

\displaystyle F_n = \frac{\phi^n - (-\phi)^{-n}}{\sqrt{5}}

で表される。分子の(-\phi)^{-n}の部分はnが大きければほぼ無視できるくらいに小さくなるので、次の近似ができる。

\displaystyle F_n \approx \frac{\phi^n}{\sqrt{5}}

あとは、\log _{10} F_n = 999のときのnを求めれば良い。

phi = (1 + sqrt(5))/2
ceiling(999 + log10(sqrt(5)))/log10(phi)