Project Euler 25

Question: 

The Fibonacci sequence is defined by the recurrence relation:

F_n = F_n−1 + F_n−2, where F₁ = 1 and F₂ = 1.

Hence the first 12 terms will be:

F₁ = 1
F₂ = 1
F₃ = 2
F₄ = 3
F₅ = 5
F₆ = 8
F₇ = 13
F₈ = 21
F₉ = 34
F₁₀ = 55
F₁₁ = 89
F₁₂ = 144

The 12th term, F₁₂, is the first term to contain three digits.

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

문제:

피보나치 수열은 아래와 같이 정의할 수 있다.

F_n = F_n−1 + F_n−2, where F₁ = 1 and F₂ = 1.

따라서, 피보나치 수열의 처음 12개는 아래와 같다.

F₁ = 1
F₂ = 1
F₃ = 2
F₄ = 3
F₅ = 5
F₆ = 8
F₇ = 13
F₈ = 21
F₉ = 34
F₁₀ = 55
F₁₁ = 89
F₁₂ = 144

12번째 피보나치 수열 F₁₂는 처음으로 세(3) 자리가 되는 첫 원소이다.

그렇다면, 천(1000) 자리가 되는 첫 피보나치 수열은 몇번째 원소일까?

Solution:

from numpy.linalg import matrix_power
import numpy, time
from itertools import count

def fib_matrix(n): # n번 피보나치 행렬을 거듭제곱 한 행렬을 array 형태로 리턴한다.
    return matrix_power(numpy.array([[1,1],[1,0]], dtype = 'longdouble'),n)

def fib(n): # n번째 피보나치 수를 int로 리턴한다.
    return int(fib_matrix(n)[0][1])

def getlength(n): # n 의 자리수를 return 한다.
    return len(str(n))

start = time.time()

for i in count(1):
    if getlength(fib(i)) == 1000: # 자리수가 1000이 될 때까지 반복한다.
        print('first 1000 digit is at index {0}, find in {1:.2f}s\n'.format(i,-start+time.time()))
        break

피보나치 수열은 다음과 같이 계산했다.

numpy 를 import 해서 array를 이용해 행렬을 표현했다.

numpy.linalg 에서 matrix_power 를 이용해서 array 로 표현한 행렬의 거듭제곱을 표현해 줬다.

numpy.array 를 사용하게되면 datatype 이 int64 가 되어, -9223372036854775808 to 9223372036854775807 까지만 표현이 가능해진다.

1000 자리수를 구하기에는 턱 없이 부족한 자리수여서 datatype 을 long double 로 바꾸어 주었다.

https://docs.scipy.org/doc/numpy/user/basics.types.html: numpy data types

0.24 초 걸렸다!

4782