Project Euler

[Clam]

http://projecteuler.net/" class="bbc_link" target="_blank">projecteuler.net

Anyone here tried this? I've mentioned the site before (in the most obscure way imaginable), but out of curiosity I looked it up again and found it's still thriving. It's a series of maths/programming puzzles that ramp up in difficulty as you go along.

I did it in Java back then, but now I'm starting again in R, which I'm learning for work. You can even see my progress!
http://projecteuler.net/profile/Clam_Spammer.png" alt="" class="bbc_img" />
(I've overtaken the meagre 26 that I solved in Java http://www.lemmingsforums.com/Smileys/lemmings/smiley.gif" alt=":)" title="Smiley" class="smiley" />)

[GuyPerfect]

Spoiler Spoiler Spoiler

I just picked a random question, http://projecteuler.net/problem=9" class="bbc_link" target="_blank">Problem 9...

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,
a² + b² = c²

For example, 3² + 4² = 9 + 16 = 25 = 5².

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

There isn't enough information here to solve the problem, meaning we're going to be left with some amount of brute force to find the triplet in question. Sooooooo... the lazy solution!

The problem defines a right triangle with a perimeter of 1000 units. Since we know the second-shortest leg of a right triangle can be up to oh-so-slightly less than the length of the hypotenuse, we know that the length of that side in this case cannot meet or exceed 1000 / 2 = 500 units, meaning an upper theoretical limit of 499.

This gives us a nested loop. For each value of a from 1 to 498, then each value of b from a + 1 to 499, which pair of values solves the problem as stated?

In JavaScript:

function triplet() {
    var a, b, c;

    // Brute force the legs of the triangle
    for (a = 1; a < 498; a++) {
        for (b = a + 1; b < 499; b++) {

            // Calculate the length of the hypotenuse
            c = Math.sqrt(a * a + b * b);

            // Reject the hypotenuse if it is non-integer
            if (c % 1) continue;

            // Check if the perimeter is 1000
            if (a + b + c == 1000)
                return "a = " + a + ", b = " + b + ", c = " + c;

        } // b
    } // a

    // A perimeter of 1000 was not found
    return "I dun' find it!";
}

The output of this function is: a = 200, b = 375, c = 425. The product, therefore, is 200 * 375 * 425 = 31875000.

[ccexplore]

Yes, I think part of the point of these problems is that some amount of computation is always required, although mathematical insights and knowledge may help reduce the amount of such computation from "brute force" to something more efficient (and I imagine with the harder problems, you may be forced to apply mathematics to render the computation tractable).

In the case of problem 9, there is Euler's formula for http://en.wikipedia.org/wiki/Pythagorean_triples#Generating_a_triple" class="bbc_link" target="_blank">Pythagorean triples that, while I don't think completely eliminates all computation, does greatly reduce the problem from the more straightforward approach you outlined (I believe to the point where you can carry out the remaining computation by hand in a matter of a minute or two [update: a quick refinement effectively gets you so close to the answer that one can say the problem can be "solved" directly]).  I supposed it is intentional for the presumably "easier" problem that a simple brute-force approach is sufficient.

I have only skimmed through some of the problems so I can be very wrong in characterizing them as follows, but it feels like Project Euler is serving a rather narrow segment of audience:  computer scientist who wants to solve more mathematical problems, and mathematicians who wants to take a break from theorem-proving.  I feel like most mathematicians might find the problems have "too much computation" while most computer scientists might quickly become a bit bored with the seeming lack of variety in the problem space (ie. most seem related to number theory, while computer science's domain is broader with studies of different algorithms and data structures like graphs and trees).

[ccexplore]

I decided to jump ahead straight to the last pages, and have found that the problems there have become more varied and interesting (and of course much more difficult).  So I take back my concerns about the problems being too narrow in its coverage of subject matters.

Perhaps that's the better way to go for the many people here who already have some background in the subject matters:  to actually start with the hardest problems and go backwards until you find one that doesn't completely stump you, and go from there.

[Clam]

There isn't enough information here to solve the problem, meaning we're going to be left with some amount of brute force to find the triplet in question. Sooooooo... the lazy solution!

That's pretty much how the game works http://www.lemmingsforums.com/Smileys/lemmings/smiley.gif" alt=":)" title="Smiley" class="smiley" />. When I said "maths/programming" I didn't mean either-or. Unless you're one of those hardcore pencil-and-paper solvers (there's actually a category for these http://www.lemmingsforums.com/Smileys/lemmings/laugh.gif" alt=":D" title="Laugh" class="smiley" />).

As for where to start - I just started from the beginning. There's a nice difficulty curve where the earlier puzzles teach you tricks that help you solve the later ones. Plus the easy puzzles score the same points as the rest http://www.lemmingsforums.com/Smileys/lemmings/wink.gif" alt=";)" title="Wink" class="smiley" />