# Project Euler programming challenges: Am I missing something?

1. Jan 23, 2014

### Jamin2112

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. Jan 23, 2014

### SixNein

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?

3. Jan 23, 2014

### Jamin2112

Let me think about that for a minute.

4. Jan 23, 2014

### Jamin2112

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

5. Jan 23, 2014

### D H

Staff Emeritus
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?

6. Jan 23, 2014

### D H

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

7. Jan 23, 2014

### SixNein

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!

Any ideas?

Last edited: Jan 23, 2014
8. Jan 23, 2014

### JorisL

if they are multiples of 3 and 5 how can you write them?

9. Jan 23, 2014

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

10. Jan 23, 2014

### AlephZero

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

11. Jan 23, 2014

### 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]

Last edited by a moderator: May 6, 2017
12. Jan 23, 2014

### Jamin2112

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

13. Jan 23, 2014

### JorisL

This is correct but now do it so you can use any range.
Because this is pretty useless as is.

14. Jan 23, 2014

### Jamin2112

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

15. Jan 23, 2014

### Jamin2112

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.

16. Jan 23, 2014

### JorisL

nope that's what I meant. ofcourse you can expand for other numbers (say 3 and 7).
Regardless the same procedure can be used.

17. Jan 23, 2014

### Jamin2112

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

18. Jan 23, 2014

### Jamin2112

On to the next problem:

Can anyone think of a non-brute-force way of doing this?

19. Jan 23, 2014

### D H

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

20. Jan 23, 2014

### Jamin2112

Do you know any site where I can find a list of problems that would make me a better programmer?