Project Euler programming challenges: Am I missing something?

  • Thread starter Jamin2112
  • Start date
  • #1
986
9
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:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.
Is there supposed to be some fancy way of doing that?
 

Answers and Replies

  • #2
SixNein
Gold Member
42
16
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?
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
986
9
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?
Let me think about that for a minute.
 
  • #4
986
9
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?
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:
Answer using brute force algorithm: 233168 (17 ns)
Answer using Gauss's Sum of Integers Formula: 266333 (2 ns)

Source code:

Code:
// 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
D H
Staff Emeritus
Science Advisor
Insights Author
15,393
685
So that's

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

For some reason, though, it's not working ....
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
D H
Staff Emeritus
Science Advisor
Insights Author
15,393
685
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:
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
SixNein
Gold Member
42
16
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:
Answer using brute force algorithm: 233168 (17 ns)
Answer using Gauss's Sum of Integers Formula: 266333 (2 ns)

Source code:

Code:
// 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;
}

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:
  • #8
489
189
if they are multiples of 3 and 5 how can you write them?
 
  • #9
Borek
Mentor
28,533
2,966
While some of the problems can be solved by brute force, others will take way too long.

Besides, brute force is for weenies.
 
  • #10
AlephZero
Science Advisor
Homework Helper
6,994
291
Besides, brute force is for weenies.
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:
 
  • #11
Borek
Mentor
28,533
2,966
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:
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:
  • #12
986
9
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?
Yea, my bad. Now it's right.

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

Code:
// 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
489
189
This is correct but now do it so you can use any range.
Because this is pretty useless as is.
 
  • #14
986
9
This is correct but now do it so you can use any range.
Because this is pretty useless as is.
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:
// 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
986
9
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
489
189
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
986
9
nope that's what I meant. ofcourse you can expand for other numbers (say 3 and 7).
Regardless the same procedure can be used.
Code:
// 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
986
9
On to the next problem:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
Can anyone think of a non-brute-force way of doing this?
 
  • #19
D H
Staff Emeritus
Science Advisor
Insights Author
15,393
685
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
986
9
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.
Do you know any site where I can find a list of problems that would make me a better programmer?
 
  • #21
DavidSnider
Gold Member
488
131
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.
 
  • Like
Likes 1 person
  • #22
SixNein
Gold Member
42
16
Do you know any site where I can find a list of problems that would make me a better programmer?
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.
 
  • #23
SixNein
Gold Member
42
16
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.
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.
 
  • #24
D H
Staff Emeritus
Science Advisor
Insights Author
15,393
685
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.
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:
 (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:
  • #25
986
9
This look right?

Code:
#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:
Sum of even Fibonacci terms up to 4000000 equals 4613732
 

Related Threads on Project Euler programming challenges: Am I missing something?

  • Last Post
Replies
22
Views
4K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
5
Views
505
Replies
20
Views
1K
  • Last Post
Replies
4
Views
808
Replies
2
Views
1K
Replies
6
Views
4K
Replies
13
Views
1K
  • Last Post
Replies
14
Views
848
  • Last Post
Replies
5
Views
2K
Top