0x0002 - Project Euler 002 – More efficient

Problem:

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.

Solutions:

1. Python Solution:

limit = 4000000
x, y, sum = 3, 5, 2

while sum < limit:
    sum += (x + y)
    x, y = x + 2*y, 2*x + 3*y

print(sum)

2. Java Solution:

class PE002
{
	public static void main(String args[])
	{
		long limit = 4000000L, x = 1L, y = 1L, sum = 0L;
		while(sum < limit)
		{
			sum += (x + y);
			x = x + 2 * y;
			y = 2 * x - y;
		}
		System.out.println(sum);
	}
}

Analysis:

We know that in the Fibonacci series, any term is the sum of the previous two terms (starting from the third term). So if we already have two terms x and y, then we can write the next term as x+y.

Extending this, we see that the next term will be the sum of y and x+y, i.e. x+2y. Thus the series can be represented as:

x, y, x+y, x+2y, 2x+3y, 3x+5y, 5x+8y, 8x+13y, 13x+21y, …

Now using the same idea that I used in an earlier method, that every third term is an even term, I can say that the sum of even terms is (x+y) + (3x+5y) + (13x+21y) + …

In the above codes, I have used the sum variable for the sum of every third term. Then I have incremented x and y so that x becomes x+2y and y becomes 2x+3y. Note that this is possible in Python because of multiple assignment operation. In Java, we have to set y to 2x-y instead of 2x+3y. This is so because x is already x+2y and assigning y the value 2x+3y will make y as 2x+5y, whereas 2x-y will make y = 2x+3y.

For instance, suppose x = 3 and y = 5. Then in Python the statement x, y = x+2*y, 2*x+3*y will set x and y to 3+2(5) and 2(3)+3(5), i.e. 13 and 21. On adding these in the next cycle, we get the even term x+y = 34 which is added to sum.

Then we place the assignment codes in a while loop, which terminates when the last term is greater than or equal to 4,000,000.

Under Python3.1 in the Ubuntu 10.10 terminal, the brute force method takes 0.101734 milliseconds, as compared to 0.0507588 milliseconds (49.89% of the time) by this method. This is much better than the earlier method as there are no floating point calculations. The brute force approach used for bench-marking is:

evenSum, a, b = 0, 1, 2
while a < 4000000:
	if b % 2 == 0:
		evenSum += b
	a, b = b, a+b
print(evenSum)