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?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Project Euler programming challenges: Am I missing something?
Loading...