Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.

Project Euler - The Puzzle Palace

October 22, 2008

If you enjoy programming puzzles (and who doesn't?) I highly recommend that you take a trip over to Project Euler. This fun site is chock-full of short problems that generally require skills in programming, math, and logic to solve. And they're constructed so that you get instant feedback on your success or failure at solving them.

The site has a nice concise description of its purpose:

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.

Project Euler had its origins as a list of problems on a math web site, and grew to the point where founder Colin Hughes spun off his own site. Over 40,000 users have submitted solutions, with entries coming from all over the world.

An Example

Just as an example,  I'll walk through problem number one, probably the simplest on the site. It reads:

Add all the natural numbers below one thousand that are multiples of 3 or 5.

As a programmer, you see no problem with solving this quickly and easily, using basically any language of your choice. C++ looks like this:

#include <iostream>
const int N=1000;
int main(int argc, char* argv[])
{
int sum = 0;
for ( int i = 0 ; i < N ; i++ )
if ( (i % 3) == 0 || (i % 5) == 0 )
sum += i;
std::cout << "Total: " << sum << "\n";
return 0;
}

Running this program pops out a solution of 233168, and if you submit that to Project Euler, you are greeted with the happy news that you have the problem solved.

There's More

Of course, the whole point of these problems is to encourage some thought about them. Might there be a more efficient way to solve the problem?

In this case it's pretty easy to cook up a nice solution that doesn't require any iteration and runs in O(1) time. It rests on a couple of fairly simple pieces of math.

First, we know how to count the number of instances of a multiple of x up to limit n: floor(n/x). So for example, to find the number of multiples of 3 less than or equal to 10, we calculate floor(10/3), for a value of 3.

But we have to sum all those values of X. You probably already know how to evaluate a sum in the form 1 + 2 + 3 + ... + N using the simple formula N*(N+1)/2. Summing the multiples of X is clearly just a matter of multiplying that formula by X.

Using my alternate programming tool, Excel, I quickly mocked up the solution for the multiples of 3 and 5 less than 1000. Of course, you'll quickly realize that there is a new issue here: Any number that is a multiple of both 3 and 5 will be counted twice. So to complete the correct solution we need to subtract all multiples of 15.

After the usual fumbling with Excel formulas I had the same answer in a closed form solution, and felt like I had this one licked.

Vindication

After you take your best shot at a problem, Project Euler has a PDF that discusses solutions, plus a discussion forum where you can see various attacks on the problem.

I was happy to see that my solution process mirrored the PDF almost perfectly. Mastering the easiest problem on the site doesn't mean much, but blowing it would have felt pretty bad.

Regardless of your skill level, you can probably have a good time on Project Euler. And wherever you are in your career or education, there's nothing wrong with improving those analytical skills, right? Enjoy!

More Insights

 To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.