Wednesday, July 23, 2014

Project Euler Q1

Hi ! 
      I'm Lahiru Karunaratne. I'm currently an undergraduate at University of Colombo. This is my attempt to solve problems posted at projecteuler.net. These problems can be solved with Mathematics or with a help of a programming language. I'm going to start from the first problem. 

Problem 1

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.

Solution 1

This is an easy question compared to the others. I found a mathematical way to solve this one. As mentioned in the problem if we listed all the natural numbers below 100 that are multiples of 3 or 5 we get following numbers,


Now you can see that, if I get the sum of multiples of 3 and sum of multiples of 5 separately and add those two values (let's call this value "S"), I'm close to the answer. But the issue is when I add up multiples of 3 it includes the multiples of 15 too. (15, 30, 45, 60, 75, 90). Fortunately this issue can be avoided by subtracting the sum of multiples of 15 from "S". So that's it we have solved the problem. Let's implement this method to the real problem. These are my steps,

  1. Getting the sum of multiples of 3 below 1000.
  2. Getting the sum of multiples of 5 below 1000.
  3. Getting the sum of 1,2 steps.
  4. Calculating the sum of multiples of 15 below 1000.
  5. Subtracting the value of 4th step from the 3rd step.
I'm using the formula for the summation of the arithmetic series,

                       
Then I got following values for above tests,

  1. 166833
  2. 99500
  3. (166833 + 99500) = 266333
  4. 33165
  5. (266333 - 33165) = 233168
The answer is 233168. 

No comments:

Post a Comment