025. 一千位斐波那契数(1000-digit Fibonacci number)

斐波那契数列定义如下:\(F_n=F_{n-1}+F_{n-2}\),其中\(F_1=1,F_2=1\),因此前十二个斐波那契数分别为以下数值:\(1,1,,2,3,5,8,13,21,34,55,89,144\)。第十二位斐波那契数是第一个超过三位数的斐波那契数,求第一个包含一千位数的是第多少个斐波那契数?

分析:这道题至少有两种解法,第一种解法是循环遍历斐波那契数列,找到第一个达到一千位的斐波那契的位数。第二种解法则是根据斐波那契数列的通项,可以直接求解出答案。第一种思路相对简单,只需要在平常求斐波那契数列的函数中加上一个位数的终止条件即可,达到了终止条件则退出循环并返回计数,即为所求。对于第二种思路,已知斐波那契数列通项为:

$$ F(n)=\frac{\phi^n-(-\phi)^{-n}}{\sqrt{5}},\ where\ \phi=\frac{1+\sqrt{5}}{2} $$

从通项公式易知,当\(n\)足够大时,\((-\phi)^{-n}\)足够小可以省略,此时\(F_n=\phi^n/\sqrt{5}\)。要求第一个达到一千位的斐波那契数,即求第一个\(n\)使得\(F_n>10^{999}\),两边取对数则有:

$$ nlog(\phi)-\frac{1}{2}log(5)>999\Rightarrow n>\frac{999+log(5)/2}{log(\phi)}\approx4781.859 $$

则第一个达到一千位的斐波那契数应为4782,和第一种思路求出的结果相同。下面是第一种思路的代码实现:

# time cost = 40.2 ms ± 412 µs

def main(N=1000):
        a,b,n = 1,1,1
        while True:
            n += 1
            a,b = b,a+b
            if len(str(a)) == N:
                return n