Project Euler Problem 1 (Java)

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

The first problem in Project Euler is very simple and straight-forward. Even though most likely unnecessary for this problem, I will still list the steps to solving it, as I will do with every problem. This first solution will be done in Java.

Definitions:

Natural Number – Integer greater than zero. (1, 2, 3, 4, 5…)

Multiple – Number that is the product of the given number and any factor. (9 is a multiple of 3)

Sum – The resulting number when multiple numbers are added together. (5 is the sum of 2+3)

Simple Approach:

Ok, so this problem asks us to find the sum of all the multiples of 3 or 5 below 1000. Naturally, we should immediately think of using a loop since it requires that we find all the numbers that match the criteria and are under 1000. So how do we loop through all the numbers under 1000? This is actually very easy.

for(int i=0; i<1000; i++)
{
    //whatever is put here will be
    //run 1000 times
}

Now, this simple loop counts from 0 to 1000, but it doesn’t really do anything yet. We want to add up a series of numbers, so we’ll have to declare a variable to contain our ever-increasing sum. Let’s call this variable sum, and make it of the integer type.

int sum = 0;
for(int i=0; i<1000; i++)
{
  sum = sum + i;
    //sum of every number from 1 to 999
}

Alright, that’s better, but we don’t actually want to sum up all the numbers, we only want to sum the multiples of 3 or 5. To do this we need an if-statement. But how do we check if a number is a multiple of another number? This is done by using the “%” modulus operator. This operator basically performs division on the numbers provided and returns the remainder. So if we did (8%5), the value 3 would be returned. So how does this help us with multiples? Well, if we took a number % 3, if the result is 0 then we know the number is a multiple of 3, and similarly with 5. We now add this check within this loop, so every number from 0 to 999 is checked. If the number is a multiple of 3 or 5, then we add it to the sum. The updated code looks like this:

int sum = 0;

for(int i=0; i<1000; i++)
{
    if((i%3 == 0) | (i%5 == 0))
  {    //if i is a multiple of 3 or 5
       //add it to the current sum
        sum += i;
  }
}

The final piece of code simply prints out the sum that we found.

System.out.println(sum);

As will always be done, I will post the final code at the end, but I will refrain from putting the actual numerical solution on here. I realize you could just compile this code and run it to find the answer, but at least that’s more work than just copying the solution from here. The point of this blog is to discuss the programming, math, and problem-solving aspects of Project Euler, not just to provide the answers. What good would that do?

Improvements:

Right now many of you are probably thinking, “There are much better ways to do this.”, and of course there are. Once you have gone to the website and entered your solution, you will be provided access to a forum where this problem is being discussed. Many of the comments there are very interesting, and many much better solutions are posted. Also, you will sometimes be given a pdf with a guide to solving the problem. These resources are very useful, and a great deal of number theory is usually discussed. I won’t always discuss these better solutions, because sometimes the math is quite heavy, but I’ll do my best to mention anything I find particularly interesting. With that being said, let’s improve our code.

Ok, first of all let’s look for some simple improvements while keeping our method the same. The most obvious one I see is to make the for loop start at 3 instead of 0. Obviously 0, 1, and 2 are not multiples of 3 or 5. That seems like it’s about the only change we can make to this method. This is a pretty simple problem and a pretty simple solution. Many people, including myself, will be content to use this solution.

However, I feel like I should mention a different approach that I found very interesting. There is actually a math formula for finding the sum of a series if you know the first term, last term, and number of terms. Basically stated, the sum of a series equals the first term plus the last, multiplied by one half of the number of terms in the series.

(sum=(first_term + last_term)*(number_of_terms/2)).

See this Wikipedia page for more details, but be warned that the explanation is a bit cryptic. So how does this math formula help us? Well, instead of having to loop through 1000 numbers, instead we can just make our program evaluate this simple formula. This will save time and computing power. So how do we turn this formula into useful Java code. Well, first let’s analyze our problem. We need to sum up the numbers that are multiples of 3, sum up the numbers that are multiples of 5, and add these two sums together. However, this sum will include all the numbers that are multiples of 15 twice, because these numbers are multiples of 3 and also multiples of 5. To fix this problem, we just need to subtract the sum of the multiples of 15. Here is what that looks like in Java:

int multOf3 = (3+999)*333/2;
int multOf5 = (5+995)*199/2;
int multOf15 = (990+15)*66/2;
//subtract multiples of 15.
int sum = (multOf3+multOf5-multOf15);

Both solutions produce the same answer, but this optimized solution requires much less work on the part of the computer. For a simple problem like this it doesn’t matter much, but if you wanted to perform a similar operation up to a billion instead of a thousand then you might want to use the optimized way.

Well, that’s it for this problem, but there will be more to come soon. This problem was pretty easy, but they get difficult pretty quickly.

Thanks for reading,

Michael

Link to Java Code(Note: some ads will be displayed, but the download is completely free)