0x0000 - 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.