Project Euler – Problem 1

Written by on 14 September 2010

Topics: Project Euler

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.

44 Comments For This Post I'd Love to Hear Yours!

  1. Nils says:

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

  2. anant says:

    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

  3. Kristian says:

    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

  4. anant says:

    Hi Kristian

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

    Thanks

    Anant

  5. Abdullah says:

    hi

    thanks mr Kristian for such best explanation with different approaches.

  6. Kristian says:

    Hi Abdullah

    Thanks šŸ™‚

  7. Anshul says:

    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

  8. Kristian says:

    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.

  9. Anshul says:

    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.

  10. Kristian says:

    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.

  11. Anshul says:

    OK.
    Thanks for the tips…Very useful…gave me a direction to go upon.
    Happy coding!!! šŸ™‚

  12. Kristian says:

    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

  13. Anshul says:

    Thanks Again…:-)

  14. Akshat says:

    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)

  15. Kristian says:

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

  16. Nitish says:

    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

  17. Nitish says:

    I included iostream but it disappeared from the comment

  18. Kristian says:

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

  19. Stefan says:

    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?

  20. Kristian says:

    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.

  21. Stefan says:

    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.

  22. siraj says:

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

  23. teen_boy says:

    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.

  24. Tegar Percy says:

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

  25. Ken says:

    So you are meant to use coding not your head ?

    Ok I feel less thick now

  26. Raj says:

    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.

  27. hb says:

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

  28. GPLTalor says:

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

  29. Reede says:

    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)

  30. Reede says:

    I’m using python

  31. rism says:

    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.

  32. rism says:

    Oh scratch that. Misread the question.

  33. Besa says:

    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

  34. Gaming ORB says:

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

  35. Vi says:

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

  36. Sierra says:

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

  37. Sierra says:

    I’m doing it by hand, btw

  38. reg says:

    it is not correct. The answer is: 233168

  39. subham says:

    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

  40. Jean-Marie Hachey says:

    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 —

  41. Jean-Marie Hachey says:

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

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

    Ex:
    {1-1000} [233168]
    {1-10000} [23331668]
    {1-100000} [2333316668]
    Etc…

  42. Jean-Marie Hachey says:

    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…

Trackbacks For This Post

  1. » Project Euler Problem 1- Find the sum of all the multiples of 3 or 5 below 1000. Kushal Dalal
  2. Code Kata – Euler Project 1 in C# – Blog of Gabriel Beedles

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.