# Project Euler – Problem 1

Now that the fluff around the coding is covered, we are ready to solve the first problem.

The description of problem 1 on Project Euler reads

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

There are multiple methods for finding the solution for this problem…

## Bruteforcing

My first suggestion to solving one of these problems, is usually to bruteforce it. In order to bruteforce the first problem, we need to iterate over all the numbers from one to 1000, and we need a way to check if the number we are checking is divisible by 3 and/or 5.

One way we can check if 3 is a divisor of x (which is declared as integer) is by the following line

`(x/3)*3 == x`

Here we use integer division, which means that we will discard the fractional part of the result. An example of integer division is 10/3 = 3.

However, this can be written much shorter using the modulo operator, which finds the remainder of the integer division. The modulo operator in C# is written %.

So instead of the previous check we can write

`x % 3 == 0`

The whole code can be written as

```int result = 0;
for (int i = 1; i < 1000; i++) {
if (((i % 3) == 0) || ((i % 5) == 0)) {
result += i;
}
}
```

And the result of running the code is

```The sum of all numbers dividable by 3 or 5 is: 233168
Solution took 0 ms
```

As you can see, for such small problems, it takes less than a millisecond on my computer to solve, so there really is not need to find faster solutions. However, lets explore the problem a bit more.

## A geometric/arithmetic approach

In the first bit of code we check if a number was divisible by 3 and/or 5, and this way we only checked each number once. Another solution would be to find the sum of all numbers divisible by three, and the sum of all numbers divisible by 5. We could define a function that did this.

```private int SumDivisbleBy(int n, int p){
...
}
```

where n is the divisor, and p is the greatest number we want to check. Which in this case p=999, and n={3,5}In this case we have counted number which are divisible by 3 and 5 twice, and therefore need to subtract them such that the solution would be

```SumDivisbleBy(3, 999) + SumDivisbleBy(5, 999) - SumDivisbleBy(15, 999)
```

However, we need to put something clever inside the SumDivisbleBy function, otherwise we have an even slower solution.

So lets look at the numbers divisible by n=3:

3+6+9+12+…+999 = 3*(1+2+3+4+…+333)

And the numbers divisible by n=5

5+10+15+20+…+995 = 5*(1+2+3+4+…+199)

The trick is to express the sum by other means, and in this case the sum

1+2+3+4+…+N = (N*(N+1)/2).

A geometric explanation is given here and an arithmetic explanation is given here. A more general explanation on arithmetic progression is given on wikipedia.

Thus the sequences for any number divisible by n can be written as n*N*(N+1)/2.

N is the highest number less than p divisible by n. In the case of 5 this is 995. However, with integer division N can be expressed as

N = p/n

Now we have all the parts needed to express an efficient solution, which in C# can be written as

```Public void Solve(){
result = SumDivisbleBy(3,999)+SumDivisbleBy(5,999)-SumDivisbleBy(15,999);
}

private int SumDivisbleBy(int n, int p){
return n*(p/n)*((p/n)+1)/2;
}
```

it is important to note the parenthesis around p/n, if these are not there, the result will deviate since the program n*below/n = n, which is different from n*(below/n).

And the output of the algorithm is once again

```The sum of all numbers dividable by 3 or 5 is: 233168
Solution took 0 ms
```

This solution can handles the sum below any given number almost equally fast, if the sum can be stored in an integer.

## Comparison

Without going into details about what happens if the numbers become greater than what can be stored in an integer or long lets have a look at the scalability of the algorithms.

Since we are looping through the all the numbers, and a two comparisons and possibly one addition is needed for each number, the algorithm scales linearly with p , which in Big O notation can be expressed as O(n), not a bad scalability as a such. However the geometric approach has a constant computation time, which is expressed as O(1), which is obviously better 🙂

## Closing remarks

Remember that the reason I wrote this, is not to give you the answer, but rather to explain different approaches to the solution. I hope you have found it useful and have learned from it. Feel free to make comments and correct mistakes. ### Posted by Kristian hsdyl

cool! Nils

Thanks a lot sir. Your explanation is really easy to understand for novice like me. anant

Hi Kristian

Pardon me for this unrelated post.

I have started solving problems on code-chef also. I am trying the problems in August Challenge. I am stuck with the problem DRANGE (Range of Data). If it is possible, could you please take a look and share what your approach could have been? Though I know they would be giving the editorials out when the contest ends, I do not find their explanation as helpful as I have found your explanation for the project euler problems.

I hope I have not offended you in any way.

Thanks
Anant Kristian

Hi Anant

I am afraid I can’t help you out on that one right now. I simply don’t have time. Besides I don’t think it is fair to give out spoilers like that when ever then contest is running.

If the problems were small you could just make an array, but I am not sure that is a feasible approach since the N can be rather large. So you will need to find a way to compress the data ranges.

And no you haven’t offended me by asking this kind of question. I take it as a compliment.

/Kristian anant

Hi Kristian

I understand. Thanks anyways. I will try to bang my head on the question.

Thanks

Anant Abdullah

hi

thanks mr Kristian for such best explanation with different approaches. Kristian

Hi Abdullah

Thanks 🙂 Anshul

Splendid Job!!!
Plz Pardon me for this unrelated post…
I just want to ask where should I start from,(Confused)…As there’s lot just then programming U hv to learn Data,Ada etc then U must knw Maths…
So are there any books(specific for Maths) which are prefectly meant for programming purpose from zero to high…As I find myself lame for questions of Higher level on Project Euler…and I don’t want to submit every sol.n after peeping into yours..
Thanks Kristian

Hi Anshul

Thank you for a great question which also warrants a great answer. First of all the programming part, it is not necessary to know more than one programming language, but there is certainly a benefit to it I think. However, programming is more than the language, there is a whole lot to learn about algorithms and data structures which is almost generic regardless of the language you program in.

One of my personal favorites for that topic is this one
http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844/

On the math side, I don’t think there is any one book or series of books that will lead you to be able to solve these problems. There are a whole lot of number theory in them, but also some linear algebra, some statistics and so on. it is even more difficult to actually recommend something without knowning your current level.

I can recommend khanacademy.org which is a great learning place that will take you far.

If what you are really looking for is some programming challenges to throw yourself at, there are a lot of options which are less math focused then Project Euler, not that I will try to discourage you by any means. You can see a whole lot of ideas right here http://www.mathblog.dk/programming-challenges/
Uva online judge, code foces as well as code chef have some really interesting problems I think. Anshul

I do use codechef…
Newbie there and doing UG in CS(2nd yr)(U asked my level-novice++).

So I think U suggested me to first study all the Programming concepts(Frm the book U suggested for efficient progrmm.)and for strengthening math go from High School level to beyond…and then switch to solving.

After that I should go on to the books you referred as containing lots of number theory,LA,stats..etc.

Is that what u meant to say???

Hope then I will turn as good as you… 🙂
Thanks for the help. Kristian

I don’t think it is that easy to answer your question. Being a cs undergrad I am pretty sure you are already having quite a few courses in different subjects.

I think there are two pieces of advice I can give you right now. The first advice here, is to have fun. You probably already have an official study plan, so things you do besides that should be fun. I don’t mean you need to sit and laugh all the time, you might even be frustrated some of the time. But somewhere deep down it should satisfy something in you to do this.

The second advice I will give you is that the most important thing to learn in order to solve problems like these are to think abstractly. This probably comes from a mixture of trying some of the problems, learning a bit of new theory while trying to solve it (google is your friend here), and reading math. Become familiar with the notation and give your self some problems where you push yourself a bit.

I know these are not specific things you can read, but I hope they do help you on your way. I will see if I can come up with some interesting reads later on. Anshul

OK.
Thanks for the tips…Very useful…gave me a direction to go upon.
Happy coding!!! 🙂 Kristian

Hi again

I was looking for something about number theory which is a very integral part of the Project Euler problems. I found this book

http://www.amazon.com/Friendly-Introduction-Number-Theory-Edition/dp/0321816196/

It is pretty expensive, but from the chapter I have skimmed, it looks pretty good.
The first 6 chapters are available here
http://www.math.brown.edu/~jhs/frint.html Anshul

Thanks Again…:-) Akshat

um…i don’t know why no ones mentioned it yet but why not use modulo? my JS code(runs fast enough)-

var num = 1000;
var total = 0;
for (var i = 0; i < num; i++) {
if (i % 3 == 0 || i % 5 == 0) {
total += i ;
}
}
console.log(total) Kristian

um… That is exactly what I do in my first solution.

[…] the project euler 1 solution. For more information about the methods and details you can check this blog which have all the […] Nitish

Hi Kristian,this is your code i translated to C++

#include

using namespace std;

long long SumDivisibleBY(long int a,long int b);

int main()
{
long long result=0;

for( int i=1;i<=99999;i++)
{
if(((i%3)==0||(i%5)==0))
{
result+=i;
}
}

cout <<SumDivisibleBY(3,99999)+SumDivisibleBY(5,99999)-SumDivisibleBY(15,99999);
return 0;
}

long long SumDivisibleBY(long int n,long int p)
{
long long j = n*(p/n)*((p/n)+1)/2;
return j;
}

I changed the upper limit to 99999 but the result by two methods came out to be different and i am wondering why? Nitish

I included iostream but it disappeared from the comment Kristian

The reason for the wrong results could happen due to integer overflow. Stefan

Sorry, I am a beginner in programming but when I compile and run the code you provided there is no result, actually if I put a printf to display the result, it shows 1000. Where is the problem? Kristian

I don’t know why it doesn’t work for you. Have you read this post http://www.mathblog.dk/project-euler-prolog/ as it gives you are little background for the the pieces of code you have to wrap around the functions I provide here in order to run. Stefan

It’s me again, thanks for your feedback.I solved the problem and your code is fine. It was from the printf I wrote wrong. Thanks and sorry for bothering you. siraj

Hi,
I amazed on your solution.I seen your code After i got my solution.I UNDERSTAND STILL IM IN CODE PLAY SCHOOL .I placed my time consuming code.How to see the time taken by code.it would be useful for others too.
THANKS.
int three = 3;
int five = 5;
int three_total,five_total,Result = 0;

//three
do
{
i++;
three_total += three * i;
}
while (three * i < 999);
//five
int j = 0;
do
{
j++;
if(!((five * j) % 3 == 0))
five_total += five * j;
}
while (five * j < 995);
Result = three_total + five_total;
Console.WriteLine("The sum of multiples of 3 and 5 number is " + (Result )); Kristian

Hi Siraj

The timing code is described here:

http://www.mathblog.dk/project-euler-prolog/

And I made an update later on here:

http://www.mathblog.dk/stopwatch-a-timing-function-in-c/ teen_boy

wow such an elaborate explanation….
can you please suggest me other sites where i can practice c pragramming
I would be grateful if you do. 🙂
Have a nice day. Tegar Percy

this is my code in C++

int jumlah=0;
int i=3, j=5;

while ( i < 1000)
{
jumlah=jumlah+3;
i+=3;
}
while ( j < 1000)
{
if(j%3!=0)
jumlah=jumlah+5;
j+=5;
} Ken

Ok I feel less thick now Raj

Would you pleas post the entire compilable C# source for the optimized solution ? I am new to C# and I cannot figure out ow to call each function ( Solve() and SumDivisibleBy() ) from my static void Main() method. hb

With python we can express the sum like :
sum([i for i in range(1000) if (i%3)*(i%5)==0]) GPLTalor

// A Map/Reduce pattern to solve this problem

namespace MapReduce
{
using c = System.Console;

public class Test
{
public static void Main()
{

Func<int, List, int> MultiplesOf = (x, range) =>
{
var answer = range.Select(r => (x % r) == 0);
return answer.Any(i => i == true) ? x : 0;
};

{
var range = new List { 3, 5 };
c.WriteLine(Enumerable.Range(1, 9).Sum(x=> MultiplesOf.Invoke(x, range)));
}

}
}
} Reede

Hello, can you tell me how I can make this code work? I tried simplifying this but I’m getting the wrong number and I don’t know why.

x=sum(range(0, 1000, 3))
y=sum(range(0, 1000, 5))
z=int(x)+int(y)
print(z)

It can get 23 if the stop number is changed, and will print 23, but when the stop number is 1000 I get 266333.

x=sum(range(0, 10, 3))
y=sum(range(0, 10, 5))
z=int(x)+int(y)
print(z) Reede

I’m using python rism

Why do you iterate 1000 times?

Why not floor(1000/3) = 333. Iterate 333 times 1*3, 2*3, 3*3 etc.
Then do the same for 1000/5 = 200 times.

Reduces the iteration from 1000 times to (333 +200) = 533. i.e. approx halve the iterations.

c#

int sum = 0;
for(var i=1;i<=(1000/3);i++)
{
sum+= (3*i);
}

etc. Tho you could also refactor that to a single fx and then do a yield return.

Either modulus is definitely not the way to go because it creates an O(n) i.e. linear algo. rism

Oh scratch that. Misread the question. Besa

my simple and modest solution:
3*1+3*2+…+3*333=x
5*1+5*2+…+5*199=y
15*1+15*2+…+15*66=z
Ans=x+y-z Gaming ORB

Wow!! Such an amazing alternate solution!
Dude you are awesome! Vi

Excuse me, but how it can be that N=p/n when N=995, p=999, and n=5?

[…] rather than a pure math solution. For a more efficient but more maths focused solution see the MathBlog post on the topic. Anyway, here is what I ended up […] Sierra

Won’t the arithmetic/geometric approach double add numbers that are both multiples of 3 and 5 (e.g. 15)? Sierra

I’m doing it by hand, btw reg

it is not correct. The answer is: 233168 subham

In
1
x % 3 == 0
The whole code can be written as

int result = 0;
for (int i = 1; i < 1000; i++) {
if (((i % 3) == 0) || ((i % 5) == 0)) {
result += i;
}
}
And the result of running the code is

1
2
The sum of all numbers dividable by 3 or 5 is: 233168
Solution took 0 ms

##the answer will be 234168, not 233168 as given here Jean-Marie Hachey

Solution to Project Euler, Problem 1, using Python (v.3.6.1)

>>> import time
>>> start_time = time.time()
>>>
>>> x = 0
>>>
>>> for i in range(1000):
… if i % 3 == 0 or i % 5 == 0:
… x += i

>>> print(x)
233168
>>>
>>> print(“— %s seconds —” % (time.time() – start_time))
— 0.01000356674194336 seconds — Jean-Marie Hachey

Digits distribution pattern in the sums of multiples of 3 and 5

{Range} [Sum of multiples of 3 and 5]

Ex:
{1-1000} 
{1-10000} 
{1-100000} 
Etc… Jean-Marie Hachey

Output of the results using extension of RosettaCode in C#

https://rosettacode.org/wiki/Sum_multiples_of_3_and_5#C.23

The sum of numbers divisible by 3 or 5 between 1 and 9 is 23
The sum of numbers divisible by 3 or 5 between 1 and 99 is 2318
The sum of numbers divisible by 3 or 5 between 1 and 999 is 233168
The sum of numbers divisible by 3 or 5 between 1 and 9999 is 23331668
The sum of numbers divisible by 3 or 5 between 1 and 99999 is 2333316668
The sum of numbers divisible by 3 or 5 between 1 and 999999 is 233333166668
Etc… Jean-Marie Hachey

As expected, if we calculate the sum of numbers divisible by 6 or 10,
a relatively simple pattern is obtained:

The sum of numbers divisible by 6 or 10 between 1 and 9 is 6
The sum of numbers divisible by 6 or 10 between 1 and 99 is 1206
The sum of numbers divisible by 6 or 10 between 1 and 999 is 124506
The sum of numbers divisible by 6 or 10 between 1 and 9999 is 12495006
The sum of numbers divisible by 6 or 10 between 1 and 99999 is 1249950006
The sum of numbers divisible by 6 or 10 between 1 and 999999 is 124999500006
Etc… Sorry but i can not understand why we subtract …
SumDivisbleBy(3, 999) + SumDivisbleBy(5, 999) – SumDivisbleBy(15, 999) CmonMan

You’re off by 1000 Ban

You could use Linq to do that: Enumerable.Range(1, 999).Where(item => item % 3 == 0 || item % 5 == 0).Sum() Jürgen

A nice MATLAB-solution is:
sum(unique([3:3:999,5:5:999])) Nikolay

Great explanation, thank you!
But if we have numbers like 15, 30 etc, which are multiples of both 3 and 5, should we add them once or twice?

[…] http://www.mathblog.dk/project-euler-problem-1/ (written by Kristian Edlund) C github.com/eagletmt/project-euler-c/blob/master/1-9/problem1.c […] Ram

public static void main(String[] args){
System.out.println(“Beginning”);
//Scanner scan = new Scanner(System.in);
Integer t = 1000;//scan.nextInt();
Integer index = 1;
Integer multiple1 = 3;
Integer multiple2=5;
Integer divider1 = t/multiple1;
Integer divider2 = t/multiple2;
Integer sum=0;
System.out.println(divider1+” “+divider2);
do{
sum=sum+index3;
if(index%3!=0&&index<divider2){
System.out.print(index);
sum=sum+index
5;
}
index++;
}while(index<=divider1);
System.out.println(“Sum : “+sum);
}