Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Project Euler programming challenges: Am I missing something?

  1. Jan 23, 2014 #1
    I recently was looking for programming challenges and it was suggested to me that I check out Project Euler. http://projecteuler.net/problems

    These all seem straight-forward to me. Or there's something I'm not understanding about them.

    For instance, problem 1:

    Is there supposed to be some fancy way of doing that?
     
  2. jcsd
  3. Jan 23, 2014 #2

    SixNein

    User Avatar
    Gold Member

    Well there is always the dumb method aka brute force. But I think the goal here is to avoid brute force algorithms for algorithms with much less complexity.

    So think about it for a second:

    Uncle Gauss the mathematician came up with this cute little trick to sum up numbers:
    ∑(i) = (n(n+1)) / 2

    So how could we use that little trick to come up with a smarter algorithm?
     
  4. Jan 23, 2014 #3
    Let me think about that for a minute.
     
  5. Jan 23, 2014 #4
    Oh, okay.

    We know that we're summing up

    3 + 6 + 9 + ... + 996 + 999 = 3(1 + 2 + 3 + ... + 332 + 333)

    and

    5 + 10 + 15 + .... + 990 + 995 = 5(1 + 2 + 3 + ... + 198 + 199)

    So that's

    3*(333*334/2) + 5*(199*200/2)

    For some reason, though, it's not working ....

    Output:

    Code (Text):

    Answer using brute force algorithm: 233168 (17 ns)
    Answer using Gauss's Sum of Integers Formula: 266333 (2 ns)
     

    Source code:

    Code (Text):

    // Prompt: http://projecteuler.net/problem=1

    #include <iostream>
    #include <time.h>

    int main (int argc, char* const argv[]) {
       
        time_t start, end;
       
        // Brute force:
        start = clock();
        int sumBrute = 0;
        for (int k = 1; k < 1000; ++k) {
            if (k % 3 == 0) {
                sumBrute += k;
            } else {
                if (k % 5 == 0)
                    sumBrute += k;
            }
        }
        end = clock();
        std::cout << "Answer using brute force algorithm: "
                  << sumBrute << " ("<< (double)(end - start) << " ns)" << std::endl;
       
        // Improved, using the fact that 1 + 2 + ... + n = n(n+1)/2:
        start = clock();
        int sumOptimized = 3*(333*334/2) + 5*(199*200/2);
        end = clock();
        std::cout << "Answer using Gauss's Sum of Integers Formula: "
                  << sumOptimized << " ("<< (double)(end - start) << " ns)" << std::endl;
       
        return 0;
    }
     
     
  6. Jan 23, 2014 #5

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    That is not working because your algorithm isn't correct.

    You can sanity check your algorithm with some smaller number N (as opposed to 1000). For example, suppose N is 20. The multiples of 3 less than or equal to 20 are 3, 6, 9, 12, 15, and 18, which sum to 63. The multiples of 5 less than or equal to 20 are 5, 10, 15, 20, which sum to 50. The multiples of 3 or 5 that are less than or equal to 20 are 3, 5, 6, 9, 10, 12, 15, 18, and 20. These sum to 98, not 63+50=113. Do you see why they don't sum to 113, and how can you fix your algorithm?
     
  7. Jan 23, 2014 #6

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    BTW, here's an "interesting" perl script to calculate the sum in Euler problem #1. This also works for other integral powers of 10 between 102 to 1018, inclusive.

    Code (Text):

    my $N = 1000;  # Or any integral power of 10 between 10^2 and 10^18, inclusive
    (my $p = ($N-1)/3) =~ s/.(.*)./2${1}4/;
    (my $q = 2*$p) =~ s/./1/;
    $sum = "$p$q";  # Add zero if you want a number.
    print "N=$N sum=$sum\n";
     
    I doubt this would garner any points with the project Euler crowd. It's more suitable for an obfuscated Perl contest.
     
  8. Jan 23, 2014 #7

    SixNein

    User Avatar
    Gold Member


    So we started out with ∑i = (n(n+1))/2

    so how did you end up with 3*(333*334/2) + 5*(199*200/2)?

    ∑3i = 3∑i = 3 ((n(n+1))/2)
    ∑5i = 5∑i = 5 ((n(n+1))/2)


    So 3 ((n(n+1))/2) + 5 ((n(n+1))/2)
    where n is equal to 1000.

    BUT WAIT!!!

    There is an intersection when 3 and 5 are factors of some number. For example, 3*5 = 15. So if we just use the above two formulas, we'll be computing 15 twice. But we only want to calculate it once!

    So now we have to start thinking about this in terms of set theory.

    Any ideas?
     
    Last edited: Jan 23, 2014
  9. Jan 23, 2014 #8
    if they are multiples of 3 and 5 how can you write them?
     
  10. Jan 23, 2014 #9

    Borek

    User Avatar

    Staff: Mentor

    While some of the problems can be solved by brute force, others will take way too long.

    Besides, brute force is for weenies.
     
  11. Jan 23, 2014 #10

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    The sad thing is, given a 4 GHz 8-core CPU, and a 16 Gb of RAM, the weenies can still do a lot of "kool" stuff by brute force, before they get bored waiting for the answer.

    And some of them even get to be "professional programmers" before they stop being weenies...

    IMO computer professionals should be forced to figure out how to do something "kool" on an 8 MHz (not GHz) CPU and 512 kb (note, kb, not Mb) of RAM, before they are let loose on modern hardware :devil:
     
  12. Jan 23, 2014 #11

    Borek

    User Avatar

    Staff: Mentor

    Agreed. And I think you are way too generous.

    256 bytes were enough for these demos (http://en.wikipedia.org/wiki/Demoscene): [Broken]







    :biggrin:
     
    Last edited by a moderator: May 6, 2017
  13. Jan 23, 2014 #12
    Yea, my bad. Now it's right.

    Code (Text):

    Answer using brute force algorithm: 233168 (21 ns)
    Answer using Gauss's Sum of Integers Formula: 233168 (1 ns)
     
    from

    Code (Text):

    // Prompt: http://projecteuler.net/problem=1

    #include <iostream>
    #include <time.h>

    int main (int argc, char* const argv[]) {
       
        time_t start, end;
       
        // Brute force:
        start = clock();
        int sumBrute = 0;
        for (int k = 1; k < 1000; ++k) {
            if (k % 3 == 0) {
                sumBrute += k;
            } else {
                if (k % 5 == 0)
                    sumBrute += k;
            }
        }
        end = clock();
        std::cout << "Answer using brute force algorithm: "
                  << sumBrute << " ("<< (double)(end - start) << " ns)" << std::endl;
       
        /* Improved, using the fact that 1 + 2 + ... + n = n(n+1)/2.
         
           sumOptimized = 3 + 5 + 6 + 9 + .... + 995 + 999
                        = (3 + 6 + ... + 999) + (5 + 10 + ... + 995) - (15 + 30 + ... + 990)
                        = 3(1 + 2 + ... + 333) + 5(1 + 2 + ... + 199) - 15(1 + 2 + ... + 66)
                        = 3(333*334/2) + 5(199*200/2) - 15(66*67/2)
         
        */
        start = clock();
        int sumOptimized = 3*(333*334/2) + 5*(199*200/2) - 15*(66*67/2);
        end = clock();
        std::cout << "Answer using Gauss's Sum of Integers Formula: "
                  << sumOptimized << " ("<< (double)(end - start) << " ns)" << std::endl;
       
        return 0;
    }
     
     
  14. Jan 23, 2014 #13
    This is correct but now do it so you can use any range.
    Because this is pretty useless as is.
     
  15. Jan 23, 2014 #14
    I think the point of these problems is that they be useless. Anyhow, I'll make it slightly less useless. Or do you want no magic numbers at all? We could make a program that finds the sum of all multiples of numbers in the set S={s1, s2, ..., sn} between 0 and N exclusive, but then you'd have to find all the pairwise products of numbers in S and it would be a really messy procedure.

    Code (Text):

    // Prompt: http://projecteuler.net/problem=1

    #include <iostream>
    #include <time.h>

    int main (int argc, char* const argv[]) {
       
        time_t start, end;
       
        const int N = 1000;
       
        // Brute force
        start = clock();
        int sumBrute = 0;
        for (int k = 1; k < N; ++k) {
            if (k % 3 == 0) {
                sumBrute += k;
            } else {
                if (k % 5 == 0)
                    sumBrute += k;
            }
        }
        end = clock();
        std::cout << "Answer using brute force algorithm: "
                  << sumBrute << " ("<< (double)(end - start) << " ns)" << std::endl;
       
        /* Improved, using the fact that 1 + 2 + ... + n = n(n+1)/2
         
           e.g.
         
           sumOptimized = 3 + 5 + 6 + 9 + .... + 995 + 999
                        = (3 + 6 + ... + 999) + (5 + 10 + ... + 995) - (15 + 30 + ... + 990)
                        = 3(1 + 2 + ... + 333) + 5(1 + 2 + ... + 199) - 15(1 + 2 + ... + 66)
                        = 3(333*334/2) + 5(199*200/2) - 15(66*67/2)
         
          for N = 1000
         
        */
        start = clock();
        int sumOptimized = 3*(((N-1)/3)*((N-1)/3+1)/2) + 5*(((N-1)/5)*((N-1)/5+1)/2) - 15*(((N-1)/15)*((N-1)/15+1)/2);
        end = clock();
        std::cout << "Answer using Gauss's Sum of Integers Formula: "
                  << sumOptimized << " ("<< (double)(end - start) << " ns)" << std::endl;
       
        return 0;
    }
     
     
  16. Jan 23, 2014 #15
    I mean, if we're really going to try and make this proper, we should change all the ints to unsigned ints, check that we're not getting overflow when the sum is too big, etc.
     
  17. Jan 23, 2014 #16
    nope that's what I meant. ofcourse you can expand for other numbers (say 3 and 7).
    Regardless the same procedure can be used.
     
  18. Jan 23, 2014 #17
    Code (Text):

    // Prompt: http://projecteuler.net/problem=1

    #include <iostream>
    #include <time.h>

    int main (int argc, char* const argv[]) {
       
        time_t start, end;
       
        int a(3), b(5), N(1000);
       
        // Brute force
        start = clock();
        int sumBrute = 0;
        for (int k = 1; k < N; ++k) {
            if (k % a == 0) {
                sumBrute += k;
            } else {
                if (k % b == 0)
                    sumBrute += k;
            }
        }
        end = clock();
        std::cout << "Answer using brute force algorithm: "
                  << sumBrute << " ("<< (double)(end - start) << " ns)" << std::endl;
       
        /* Improved, using the fact that 1 + 2 + ... + n = n(n+1)/2
         
           e.g.
         
           sumOptimized = 3 + 5 + 6 + 9 + .... + 995 + 999
                        = (3 + 6 + ... + 999) + (5 + 10 + ... + 995) - (15 + 30 + ... + 990)
                        = 3(1 + 2 + ... + 333) + 5(1 + 2 + ... + 199) - 15(1 + 2 + ... + 66)
                        = 3(333*334/2) + 5(199*200/2) - 15(66*67/2)
         
          for N = 1000
         
        */
        start = clock();
        int sumOptimized = a*(((N-1)/a)*((N-1)/a+1)/2) + b*(((N-1)/b)*((N-1)/b+1)/2) - (a*b)*(((N-1)/(a*b))*((N-1)/(a*b)+1)/2);
        end = clock();
        std::cout << "Answer using Gauss's Sum of Integers Formula: "
                  << sumOptimized << " ("<< (double)(end - start) << " ns)" << std::endl;
       
        return 0;
    }
     
     
  19. Jan 23, 2014 #18
    On to the next problem:

    Can anyone think of a non-brute-force way of doing this?
     
  20. Jan 23, 2014 #19

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Don't go overboard. Those Project Euler problems are small numerical problems. Integer programming, in particular. You are not going to run into many of these problems in real life. With a few exceptions, they are not going to make you a better programmer. The key exception is that these problems might teach you to recognize up front rather than after the fact why your initial cut at the non-summed solution was wrong.
     
  21. Jan 23, 2014 #20
    Do you know any site where I can find a list of problems that would make me a better programmer?
     
  22. Jan 23, 2014 #21

    DavidSnider

    User Avatar
    Gold Member

    Not all of Project Euler is small numerical problems. DH is right though, these sorts of problems will make you fairly good at writing algorithms but teach you nothing about constructing and maintaining large real world applications.

    The only way I know of to do that is to get real world experience. Contributing to open source projects is a good way to do this before you start your career.
     
  23. Jan 23, 2014 #22

    SixNein

    User Avatar
    Gold Member

    Being a good programmer is being good at algorithms and data structures. So take the first problem as an example, bad programmers would go with the dumb method of brute force. Good programmers try to find algorithms with less complexity. The reason is due to the simple fact that algorithms with less complexity run faster and often use less resources.

    The method I was leading you towards has a complexity of O(1) which means it will do the same amount of work regardless of the size of input. A brute force method on the other hand has a complexity of o(n). So it has to do more and more work as n grows.

    Doing smart algorithms is paramount to being a good programmer. Suppose we had a lot of problems similar to these and selected brute force for them. In a real application, it will bog down resources very fast.
     
  24. Jan 23, 2014 #23

    SixNein

    User Avatar
    Gold Member

    If the goal is to be a better software engineer, I would recommend learning UML. Take a project from a use case diagram to production following UML rigorously. Learn how to write a SRS, SDD, and do some V&V testing. And most importantly, don't write it for yourself.

    Open source doesn't necessarily help one become a better software engineer. The real challenge to software engineering is to develop software according to customer requirements instead of your own. Open source isn't geared to creating business value. It's more about a few developers (often times just one) who want to write software their way and HOPE its useful.
     
  25. Jan 23, 2014 #24

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    That's a good programmer. Even better programmers realize that someone has to maintain the code. If you want to be a top-notch programmer, you will write code that is maintainable so that you can attack other interesting problems. If you make your code so overly optimized that only you can understand it, you are the one who will be stuck maintaining it.

    The second Project Euler problem is a good example. There are only eleven terms to be summed. A brute force algorithm will work quite fine here. A slight tweak that recognizes that the even elements of the Fibonacci sequence are separated by two odd elements is something that a maintenance programmer could understand. On the other hand, recognizing that the desired sum is itself closely related to the Fibonacci sequence and optimizing for that is something that a maintenance programmer will foul up.

    The desired sum of the even Fibonacci terms up to and including N can be expressed rather compactly as

    Code (Text):

     (1+Fibonacci(2+3*floor(floor(log(N*sqrt(5))/log((1+sqrt(5))/2))/3)))/2
     
    For example, with N=4000000,
    http://www.wolframalpha.com/input/?...))/Log((1+sqrt(5))/2)]/3]])/2+where+N=4000000

    Do you really want to do that?
     
    Last edited: Jan 23, 2014
  26. Jan 23, 2014 #25
    This look right?

    Code (Text):

    #include <iostream>

    // Prompt: http://projecteuler.net/problem=2

    int main (int argc, char* const argv[]) {
       
        int N = 4000000;
        int previousFib(1), thisFib(2);
        int sum = 0;
        while (thisFib <= N) {
            if (thisFib & 1 == 0)
                sum += thisFib;
            int temp = thisFib;
            thisFib += previousFib;
            previousFib = temp;
        }
        std::cout << "Sum of even Fibonacci terms up to " << N << " equals " << sum << std::endl;
       
        return 0;
    }
     

    ----------------------------------------------------------------------------------------------------------------------------

    Code (Text):
    Sum of even Fibonacci terms up to 4000000 equals 4613732
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook