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.

cool!

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

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

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

Hi Kristian

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

Thanks

Anant

hi

thanks mr Kristian for such best explanation with different approaches.

Hi Abdullah

Thanks š

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

Plz reply…

Thanks

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.

Thanks for replying…

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.

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.

OK.

Thanks for the tips…Very useful…gave me a direction to go upon.

Happy coding!!! š

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

Thanks Again…:-)

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)

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

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?

could you please explain

I included iostream but it disappeared from the comment

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

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?

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.

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.

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 ));

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/

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.

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;

}

So you are meant to use coding not your head ?

Ok I feel less thick now

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.

With python we can express the sum like :

sum([i for i in range(1000) if (i%3)*(i%5)==0])

// 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)));

}

c.ReadLine();

}

}

}

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)

I’m using python

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.

Oh scratch that. Misread the question.

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

Wow!! Such an amazing alternate solution!

Dude you are awesome!

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

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

I’m doing it by hand, btw