Channels ▼

Mark Nelson

Dr. Dobb's Bloggers

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.

About Project Euler

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!

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips 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.
 


Video