Project Euler 25

题目

$1000$-digit Fibonacci number

The Fibonacci sequence is defined by the recurrence relation: $$F_1=1F_2=1$$ $$F_n=F_{n-1}+F_{n-2}$$ Hence the first $12$ terms will be: $$\begin{array}{rl}{F}_1& =1\\ F_2& =1\\ F_3& =2\\ F_4& =3\\ F_5& =5\\ F_6& =8\\ F_7& =13\\ F_8& =21\\ F_9& =34\\ F_{10}& =55\\ F_{11}& =89\\ F_{12}& =144\end{array}$$

The $12\text{th}$ term, $F_{12}$, is the first term to contain three digits.

What is the first term in the Fibonacci sequence to contain $1000$ digits?

解决方案

利用 Python 可以做大数运算的特点，直接迭代运算。

代码

from itertools import count

N = 1000
a = b = 1
for i in count(1, 1):
    if len(str(a)) == N:
        ans = i
        break
    a, b = b, a + b
print(ans)