An elegant solution to the Fibonacci problem.
from math import sqrt, pow
def fib(n):
phi = (1 + sqrt(5))/2
return int((pow(phi, n) - pow(1 - phi, n))/sqrt(5))
if __name__==’__main__’:
i = 3
sum = 0
stop = 4000000
while True:
curr = fib(i)
if curr > stop: break
sum = sum + fib(i)
i = i + 3
print sum
Unlike the other solutions I found online, mine is not done through brute-force. To generate the Fibonacci number at index i, you don’t need to loop through the sequence until i. There is a closed form solution to this. For even-numbers in the sequence, it’s rather simple. An even number occurs with index 3, 6, 9, 12, 15, … Notice a pattern? I hope you do. :)
