f3 - Fibonacci For Fun

Even Fibonacci Sum

Project Euler #2:

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.

Solutions

Recursive

# fib_01.py
from functools import cache


@cache
def fib(n):
    return n if n < 2 else fib(n - 2) + fib(n - 1)


def even_fib_sum(n):
    i = s = 0
    while True:
        f = fib(i)
        if f > n:
            return s
        if f % 2 == 0:
            s += f
        i += 1


# Time spent: 3.153654ms

Recursive with iterator tools

# fib_02.py
from functools import cache
from itertools import accumulate, cycle, takewhile


@cache
def fib(n):
    return n if n < 2 else fib(n - 2) + fib(n - 1)


def even_fib_sum(n):
    return sum(
        takewhile(
            lambda f: f <= n,
            filter(
                lambda f: f % 2 == 0,
                map(fib, accumulate(cycle([1]))),
            ),
        )
    )


# Time spent: 2.995692ms

Iterative

# fib_03.py
def even_fib_sum(n):
    s, a1, a2 = 0, 1, 2
    while a2 <= n:
        if a2 % 2 == 0:
            s += a2
        a2, a1 = a1 + a2, a2
    return s


# Time spent: 1.154399ms

Iterative 3 by 3

# fib_04.py
def even_fib_sum(n):
    s = 0
    a1, a2, a3 = 1, 1, 2
    while a3 <= n:
        s += a3
        a1 = a2 + a3
        a2 = a1 + a3
        a3 = a1 + a2
    return s


# Time spent: 0.306553ms

Iterative 3 by 3, result at the end

# fib_05.py
def even_fib_sum(n):
    a1, a2, a3 = 1, 1, 2
    while a3 < n:
        a1 = a2 + a3
        a2 = a1 + a3
        a3 = a1 + a2
    return (a2 - 1) // 2


# Time spent: 0.234390ms

Iterative using the golden ratio

# fib_06.py
from math import log, sqrt


def even_fib_sum(n):
    if n < 1:
        return 0
    phi = (1 + sqrt(5)) / 2
    N = (log(n) + log(5) / 2) // log(phi) + 1
    num = (pow(phi, N) - pow(1 - phi, N)) // sqrt(5)
    if num > n:
        N -= 1
    N += 2 - (N % 3)
    return ((pow(phi, N) - pow(1 - phi, N)) // sqrt(5) - 1) / 2


# Time spent: 0.011343ms