Project Euler Problem 25
フィボナッチ数列で1000桁になる最初の項は何番目か?
フィボナッチ数列は以下の漸化式で定義される:, ただし .
最初の12項は以下である.
12番目の項, が3桁になる最初の項である.
1000桁になる最初の項の番号を答えよ.
1000-digit Fibonacci number
The Fibonacci sequence is defined by the recurrence relation:, where and .
Hence the first 12 terms will be:
The 12th term, , is the first term to contain three digits.
What is the first term in the Fibonacci sequence to contain 1000 digits?
考え方
フィボナッチ数列の一般項は次の式で表される
ただし、 は黄金比。この式の第2項は n = 0 のときの が最大で、それを超えることはない。従って、第2項を略した次の式は Fn の値を 0.447 以下(n > 4 のとき1%以下)の誤差で与える近似式である。
この誤差は 0.5 より小さいので、Fn の正確な整数値は以下の式で得られる。
ただし、 は床関数。
1000桁になるということは、
なので、
の解を求めればよい。
なので
なので
よって
を求める