Project Euler Problem #2

Continuing the beginning stretch of Project Euler problems, we see Problem #2: The first of many questions to feature the Fibonacci sequence.

Project Euler Problem #2: Even Fibonacci Numbers
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.

Here is a solution I found for this problem:

Solution #1: Basic Iterative Approach

The simplest solution I could think of involves checking all Fibonacci numbers less than 4,000,000 and adding the even ones to a running total. Rather than recursively generating each successive Fibonacci term, we can iteratively generate new terms by constantly updating two variables.

If we let the variable first be the nth term and we let the variable second be the (n+1)th term, then to generate the next Fibonacci number, we can store the value of second in a temporary variable, update the value of second to the sum of first and second, and finally update the value of first to the initial value of second which we stored in the temporary variable. Now the (n+1)th term will be stored in first and the (n+2)th term will be stored in second and the iteration will be complete.

Here is an implementation of this method in Python 2.7:

'''
 Author: Walker Kroubalkian
 Iterative Approach to Project Euler Problem #2
 '''
 import time
 def projectEulerProblemTwo(n):
     total = 0
     first = 1
     second = 1
     while(second<=n):
         temp = second
         second+=first
         first = temp
         if(first%2==0):
             total+=first
     return total
 start = time.time()
 print projectEulerProblemTwo(4000000)
 print("--- %s seconds ---" % (time.time() - start))
 '''
 Prints
 4613732
 --- 1.21593475342e-05 seconds ---
 for input of n = 4000000
 '''

That’s all for today, folks. Thanks for reading!