problem-002.py

"""
Question
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2: 1,2,3,5,8,13
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms."""
# 777097th person to solve the problem. 

import time

# Idea1: DP
MILLION = 10**6
N = 4 * MILLION
prev, pprev = 1, 1
s = 0
t1 = time.perf_counter(), time.process_time()
while True:
    cur = prev + pprev
    pprev = prev
    prev = cur
    if cur > N:
        break
    if not (cur & 1):
        #print(cur)
        s += cur
t2 = time.perf_counter(), time.process_time()
print(f"DP Solution")
print(f" Real time: {t2[0] - t1[0]:.10f} seconds")
print(f" CPU time: {t2[1] - t1[1]:.10f} seconds")
print()
print(s)
print("----------------")

# Idea 2: Mathematical
"""
Idea1: The idea is that ratio of successive numbers in fibonacci seq approaches the golden ratio. 
Idea2: 1,2,3,5,8,13,21,34... i.e. every 3rd number is Even.
"""

PHI = 1.61803398875 
PHI_EVEN = PHI * PHI * PHI # every third term is even
prev = 2
cur = 1
s = prev
t1 = time.perf_counter(), time.process_time()
while True:
    # keep rounding to closest integer
    cur = round(prev * PHI_EVEN)
    if cur > N:
        break
    #print(cur)
    s += cur
    prev = cur
print(f"Mathematical Solution")
print(f" Real time: {t2[0] - t1[0]:.10f} seconds")
print(f" CPU time: {t2[1] - t1[1]:.10f} seconds")
print()
print(s)
print("----------------")