フィボナッチ数が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
ところで、フィボナッチ数の一般項はよく知られているようにとして、
で表される。分子のの部分はnが大きければほぼ無視できるくらいに小さくなるので、次の近似ができる。
あとは、のときのnを求めれば良い。
phi = (1 + sqrt(5))/2 ceiling(999 + log10(sqrt(5)))/log10(phi)