Project Euler 002

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:

from math import sqrt

limit, current, sum = 4000000, 2, 0
phi3 = ((1+sqrt(5))/2)**3

while sum < limit:
        sum += current
        current = round(phi3*current)

print (sum)

2. Java solution:

class PE002
{
	public static void main(String args[])
	{
		long limit = 4000000L, f = 2L, sum = 0L;
		double phi3 = Math.pow((1 + Math.sqrt(5)) / 2, 3);
		while(sum < limit)
		{
			sum += f;
			f = Math.round(phi3*f);
		}
		System.out.println(sum);
	}
}

Analysis:

The brute-force approach would be to generate terms of the sequence and add terms with even value to get the result.

However, if you observe the Fibonacci sequence, you’ll find that every third term is an even term. In other words, an even term shows up after two terms. So instead of checking each term for divisibility by 2, we can add every third number to the sum. Notice that the series starts with 1 and 2, not 0 and 1.

An amazing fact about the Fibonacci sequence is that the ratio of any term and its previous term is approximately constant (especially for the higher numbers). This constant is the fascinating Golden ratio. So if we divide the term ‘n+1’ by the term ‘n’, we find the result to be equal to the Golden ratio. Using this, given a term n, we can find the term n+1 as T(n+1) = T(n) * phi, where ‘phi’ is the Golden ratio. Now phi has the value (1+sqrt(5))/2, which is 1.6180339887… So the resultant value of T(n+1) has to be rounded off to the nearest integer to get the correct value.

From the formula of T(n+1), we can derive the formula for T(n+2) as T(n+2) = T(n+1) * phi = (T(n) * phi) * phi

Thus, T(n+2) = T(n) * phi²

And T(n+3) = T(n) * phi³

So, the sum of all even terms in the sequence can be calculated by adding T(n), T(n+3), T(n+6), … i.e. T(n), T(n)*phi³, T(n)*phi⁶, … which is easily achieved by a while loop, with the limit as 4,000,000.

The brute-force program I used for bench-marking:

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

The time taken by the brute-force approach in Python 3.1 in the Ubuntu 10.10 terminal is approximately 0.101734 milliseconds as compared to 0.0601809 milliseconds (59.15% of the time) by the approach explained above. 

According to me, this approach can be made more efficient if the floating point calculations can be reduced/replaced.

Project Euler 001

Problem:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

Solutions:
1. Python solution:

def sum_n(n, d) :
    n = int(n/d)
    return int(d * n * (n + 1) / 2)

print (sum_n(999, 3) + sum_n(999, 5) - sum_n(999, 15))

2. Java solution:

class PE001
{
	public static int sum_n(int n,int d)
	{
		n = (int)(n/d);
		return (int)(d * n * (n + 1) / 2);
	}

	public static void main(String args[])
	{
		System.out.println(sum_n(999, 3) + sum_n(999, 5) - sum_n(999, 15));
	}
}

3. Perl solution:

use warnings;
use strict;
sub sum_n
{
	my ($n, $d) = @_;
	$n=int($n/$d);
	return(int($d * $n * ($n + 1) / 2));
}

print (sum_n(999, 3) + sum_n(999, 5) - sum_n(999, 15));

4. C++ solution:

#include <iostream>
using namespace std;

int sum_n(int n, int d)
{
	n = int(n/d);
	return int(d * n * (n + 1) / 2);
}

int main()
{
	cout<<(sum_n(999, 3) + sum_n(999, 5) - sum_n(999, 15));
	return 0;
}

5. Ruby solution:

def sum_n(n, d)
	n=n/d;
	return (d * n * (n + 1) / 2);
end

puts(sum_n(999, 3) + sum_n(999, 5) - sum_n(999, 15));

Analysis:

The brute-force approach of this problem would be to traverse through the list of numbers from 3 to 1000 and check for each number, its divisibility by 3 or 5. In the program above, I have used the inclusion-exclusion principle to find the sum of numbers divisible by 3, the sum of numbers divisible by 5 and the sum of numbers divisible by 15. Then subtracted the sum of numbers divisible by 15 as it has already been counted once in either the sum of numbers divisible by 3 or 5.

Now, to find the sum of first n positive numbers, we use the formula: S = n(n+1)/2.
For example, the sum of 1+2+3+4+5 = 5(6)/2 = 15. Suppose the terms are in an Arithmetic Progression (AP) with the first term as 3 and the common difference 3. Then the progression will be: 3, 6, 9, 12, 15. The sum of these terms is 3+6+9+12+15 = 3(1+2+3+4+5) = 3(5(6)/2) = 3(15) = 45.

Let’s modify the case a bit now. We need to find the sum of all terms less than 10 which are divisible by 3. The number of terms less than 10 which are divisible by 3 is given by 10/3 = 3, and in general, the number of terms less than n that are divisible by d is given by n/d. So, the sum will be 3+6+9 = 3(1+2+3) = 3(3(4)/2) = 3(6) = 18. Thus, the formula is S = d((n/d)((n/d)+1)/2). If we substitute n/d as m, then S = d(m(m+1)/2).

To check its validity, we substitute the limit n as 100 and the number d, with which divisibility is to be checked, as 5. Then, the sum S is 5((100/5)((100/5)+1)/2) = 5(20(21)/2) = 1050, which is the result one would get by the brute-force approach.

The time taken by the brute-force approach in Python is approximately 0.344038 milliseconds as compared to 0.032902 milliseconds (9.56% of the time) by the approach explained above. The brute-force program that I used for bench-marking is:

print(sum([x for x in range(1,1000) if x%3==0 or x%5==0]))

I have used Python 3.1 in Ubuntu 10.10 terminal for both approaches.

Project Euler

I find Project Euler a very useful website for practicing a new programming language and finding about new algorithms.

I had started solving problems a few months back with Java and am now doing them with Python and Perl. I’ll try and post most of my codes here on my blog, along with the algorithm and, if possible, some comments and performance analysis. Also, I’ll be posting the same solution in different languages.

However, for obvious reasons, I will not post the answers. Hope you all find this worthwhile!