projecteuler25--fibnacci数列

2017-08-04

1000-digit Fibonacci number

Problem 25

The Fibonacci sequence is defined by the recurrence relation:

Fn = Fn−1 + Fn−2, where F1 = 1 and F2 = 1.

Hence the first 12 terms will be:

F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144

The 12th term, F12, is the first term to contain three digits.

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

Fibonacci数列用f(n)来表示

f(n) = f(n-1)+f(n-2)

也可以用通项公式来表示,得到通项公式的证明过程可以通过维基百科来得到
$$
f(n) = \sqrt 5/5 ∗[((1+\sqrt 5)/2)^n-((1-\sqrt 5)/2)^n]
$$
其实很容易发现的一点是当n足够大的时候，减号后面部分的值会接近无穷小，最后以至于忽略不计，这道题里面当结果有1000位的时候，说明n已经达到了这个效果

因为f(1) = 1,那么我们就可以近似认为f(n)是一个以$(\sqrt 5+1)/2$为比例的等比数列

1000位整数，就相当于是最小为$10^{999}$，那么我们就可以找到一个转化这两个比例的方式，来找到n到底是多少

1	print log(10, (1+sqrt(5))/2)*999

通过这个代码可以得到结果是

1	4780.18699481

那么就是说$f(1)∗((\sqrt 5+1)/2)^{4780.18699481}$次等于$10^{999}$，那么就是说至少要4781次方，那么因为是从f(1)开始，所以最小的是f(4782).

所以这道题目是4782.

当然我自己一开始是用大整数暴力计算的。。。第一次用python写这个，发现一个很严重的bug，不能直接a = b在b是数组的情况下直接赋值，这得到的是空间的地址，也就是说修改a的时候b也被修改了。。。只能重新定义一个a

def add(digits1, len1, digits2, len2):
    more = 0
  #  print digits1[0:len1], digits2[0:len2]
    len = max(len1, len2)
    digits = [0 for i in range(0, digits1.__len__())]
    for i in range(0, len):
        more = digits1[i] + digits2[i] + more
        digits[i] = more % 10
        more = more / 10
    if more > 0:
        digits[len] = more
        len += 1
    return digits, len
def euler25(k):
    f1 = f2 = [0]*1005
    f1[0] = f2[0] = 1
    len1 = len2 = 1
    index = 2
    while True:
        tmp, tmp_len = add(f1, len1, f2, len2)
        f1 = f2
        len1 = len2
        f2 = tmp
        len2 = tmp_len
        index += 1
        if tmp_len >= k:
            break
    print f2[0:len2]
    print index
    
euler25(1000)
print log(10, (1+sqrt(5))/2)*999