Thursday 1 January 2015

Sum of even Fibonacci numbers below 4 million


Question: We know that fibonacci sequence is 0,1,1,2,3,5,8,13........ This is obtained by taking the first two whole numbers 0, 1 and then we add them we get 1, so the sequence becomes 0,1,1 now consider the two numbers 1,1 and this gives 2 and in this way the sequence is obtained. For further more information you can find about fibonacci sequence here: Fibonacci Sequence.

Let us assume the first 10 Fibonacci numbers(Neglect 0 and 1): 1,2,3,5,8,13,21,34,55,89. Now the even Fibonacci numbers become: 2,8,34. And the sum is 44. In this way we have to find the sum of even fibonacci numbers where the largest number in the group(In the top ten Fibonacci numbers is 34) is less than 4 million. 
Answer: I have commented the code and tried to make it as simple as possible. Please do contact me if you have a solution which is a way different from this so that it can be published here. Also please do comment if you have a doubt. Doubts are dangerous.


#Function to check if number is even.
#Returns True if even and else False
def is_even(n):
        if n%2 == 0:
                return True
        else:
                return False

#Function to generate n fibanocci numbers
def fibanocci(n):
        a = 0
        b = 1
        numbers = []
        numbers.append(a)
        while len(numbers) < n+2:
                numbers.append(b)
                temp = a
                a = b
                b = a+temp
        del numbers[0]
        del numbers[1]
        return numbers

#Function to generate even fibanocci numbers
def even_fibanocci(n):
        lis = fibanocci(n)
        even = []
        for i in lis:
                if is_even(i):
                        even.append(i)
        return even
#Iteration to generate sum of even numbers
j = 1
while True:
        lis = even_fibanocci(j)
        if len(lis) > 0:
                if lis[len(lis)-1] < 4000000:
                        lis = even_fibanocci(j)
                        largest = "Sum(even) of first",j,"fibonacci number is",sum(lis)
                else:
                        break
        j += 1
print largest
Output:

('Sum(even) of first', 34, 'fibonacci number is', 4613732)

So the answer for the question is 4613732. Note: This problem was taken from Project Euler. And the solution is my own.

No comments:

Post a Comment