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

Friday, August 1, 2008

Even-valued Fibonacci terms summation

Problem #2 of Project Euler

Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million.

Analysis
The first 10 terms of Fibonacci sequence are
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

We need to add the even numbers terms
2 + 8 + 34, ...

Solution:

def sumEvenFibonacci( limit ):
    a, b = 1, 1
    sum = 0
    while b < limit:
        if b%2 == 0: sum += b
        a, b = b, a + b
    return sum

Usage:

print sumEvenFibonacci( 4000000 )
If you are interested in listing all the Fibonacci numbers less than a given limit, read this article.

Thursday, July 31, 2008

Generate Fibonacci numbers with Python

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, ...

Mathematically, we write it as:
F(n) = F(n) + F(n-1)

This can easily be done in Python, using generators.
def Fibonacci(n):
    a, b = 1, 1
    while b < n:
        yield b
        a, b = b, a + b
To print all the Fibonacci numbers less than 4000000,
for i in Fibonacci(4000000):
    print i,
Output:
>>> 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578