Showing posts with label Fibonacci. Show all posts
Showing posts with label Fibonacci. Show all posts

Thursday, 1 January 2015

Fibonacci Sequence

Question: Fibonacci sequence starts from 0,1 and their sum is 1 and the sum of 1,1 is 2 and this continues. See the picture and you will understand:

In the similar way using python generate first 15 Fibonacci numbers.

Answer: I have used functional approach. If you don't know what functions are, then remove the first line with def fibanocci(n): and then instead of n add the number of Fibonacci numbers you want. This will give you the result. But I suggest you to use functions as you write the code once and generate the output the required times. You can even test your answer with the question example(if given). I wrote the code such that it will be easy to understand, but if you don't understand please do ask me I will explain. Also post your Fibonacci code.


#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
        return numbers
print fibonacci(15)
Output:

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987]

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.