Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

문제는 심플하다. 피보나치수를 구해서 400만 이하의 모든 항의 합을 구한다.

피보나치 수열에 대한 설명은 이미 다 아시리라 생각하고 생략을…

def fibonacci(num):  
    results = [1, 2, ] # 조건에서 미리 주어진 초항 1,2는 미리 넣어두자!
    n = 2
    while(results[n-2] + results[n-1] <= num):
        results.append(results[n-2] + results[n-1])
        n += 1
    return results

def euler002(n"최대 숫자"=4000000):
    result = 0
    fibo = fibonacci(n) # 4000000 이하의 모든 숫자를 구한다.
    for num in range(1, len(fibo), 3): # 피보나치 수열에서 짝수는 2를 시작으로 3개 단위로 나온다.
        result += fibo[num]
    return result

이 방식 말고 피보나치 수열의 일반항을 이용해서 풀어보았다.

def fibonacci(n):
    return int((1/5**(0.5))*(((1+5**0.5)/2)**n-((1-(5**0.5))/2)**n))

def fibonaccis(num):  # number 보다 작은 숫자까지 생성
    results = [1,2]
    n = 2
    while(results[n-2] + results[n-1] <= num):
        results.append(fibonacci(n+2))
        n += 1
    return results

def euler002a(n=4000000):
    result = 0
    fibo = fibonaccis(n)
    for num in range(1, len(fibo), 3):
        result += fibo[num]
    return result

피보나치의 일반항은 아래의 식과 같다.

\($ \\ \begin{align} a_{n+2} =&\ a_{n+1} + a_n \\ a_{n+2}-pa_{n+1} =&\ q\left(a_{n+1}-pa_n\right) \\ a_{n+1}-pa_n =& \ q^{n-1}\left(a_2-pa_1\right) \\ a_{n+1}-pa_n =&\ q^{n-1}\left(1-p\right) \\ a_{n+1}-pa_n =&\ q^n\\ a_{n+1}-qa_n =&\ p^n \\ \left(p-q\right)a_n =&\ p^n-q^n \\ p,q =&\ \frac{1\pm\sqrt{5}}{2} \\ p-q =&\ \sqrt{5}, \ \text{if p > q} \\ \therefore &\frac{ \left\{\left(\frac{1+\sqrt{5}}{2}\right)^n- \left(\frac{1-\sqrt{5}}{2}\right)^n\right\} }{\sqrt{5}} \end{align} \\\)$

이 식을 Binet’s formular라고 한다..

def fibonacci(n):
    return int((1/5**(0.5))*(((1+5**0.5)/2)**n-((1-(5**0.5))/2)**n))

def fibonaccis(num):  # number 보다 작은 숫자까지 생성
    results = [1,2]
    n = 2
    while(results[n-2] + results[n-1] <= num):
        results.append(fibonacci(n+2))
        n += 1
    return results

def euler002a(n=4000000):
    result = 0
    fibo = fibonaccis(n)
    for num in range(1, len(fibo), 3):
        result += fibo[num]
    return result

식의 유도는 괴랄하지만 우리는 수학자가 아니므로 결과만 가져다 사용하자 ㅎㅎ.