DEV Community

Discussion on: Project Euler #2 - Even Fibonacci numbers

Collapse
 
aspittel profile image
Ali Spittel

OOhh Project Euler problems are my favorite!

"""
Even Fibonacci numbers: Project Euler Problem 2
Solution in Python

https://projecteuler.net/problem=2

Takes 0.4s on my computer
"""
def fibonacci_sequence(n):
    numbers = [0, 1]

    while numbers[-1] < n:
        numbers.append(numbers[-1] + numbers[-2])

    return numbers


def sum_even_fibonacci_numbers(n):
    # O(N) Complexity
    sequence = fibonacci_sequence(n)
    sequence = [n for n in sequence if n % 2 == 0]
    return sum(sequence)

print(sum_even_fibonacci_numbers(4000000))
Collapse
 
presto412 profile image
Priyansh Jain

I tried timing your algorithm, with couple other implementations I wrote. One was recursive, one was iterative. Check this out.

# recursive
def recursive_fibonacci(num, prev_num, sum=0):
    if num % 2 == 0:
        sum += num
    if num < 4000000:
        return recursive_fibonacci(num + prev_num, num, sum)
    return sum

# iterative
def iterative_fibonacci(num, second_num):
    sum = 0
    while num < 4000000:
        if num % 2 == 0:
            sum += num
        temp = num
        num += second_num
        second_num = temp
    return sum

# Other
def fibonacci_sequence(n):
    numbers = [0, 1]

    while numbers[-1] < n:
        numbers.append(numbers[-1] + numbers[-2])

    return numbers


def sum_even_fibonacci_numbers(n):
    # O(N) Complexity
    sequence = fibonacci_sequence(n)
    sequence = [n for n in sequence if n % 2 == 0]
    return sum(sequence)

import time

start_time_recursive = time.time()
print(recursive_fibonacci(1, 1))
print("--- Recursive %s seconds ---" % (time.time() - start_time_recursive))

start_time_iterative = time.time()
print(iterative_fibonacci(1, 1))
print("--- Iterative %s seconds ---" % (time.time() - start_time_iterative))

start_time_other = time.time()
print(sum_even_fibonacci_numbers(4000000))
print("--- Other %s seconds ---" % (time.time() - start_time_other))

The output was interesting!