# Euler 9

So the other night I was a bit bored and decided to do something to pass the time. I first came across Project Euler a while ago, but had never gone further than problem #1. Boredom is a great motivator and I went through problems #2 thru #9 last night and I decided to post my solutions in search of better ones. Feel free to comment with your suggestions.

Project Euler’s Problem #9 statement is —

A Pythagorean triplet is a set of three natural numbers, $latex a < b < c$, for which,

[latex]a^{2} + b^{2} = c^{2}[/latex]

For example, $latex 3^{2} + 4^{2} = 9 + 16 = 25 = 5^{2}$.

There exists exactly one Pythagorean triplet for which [pmath]a + b + c = 1000[/pmath].

Find the product [pmath]abc[/pmath].

Butt ugly, super slow, brute-force solution:

```
from sys import exit
def is_triplet(a, b, c):
if a < b and b < c:
return a ** 2 + b ** 2 == c ** 2
for a in range(0, 1000):
for b in range(a + 1, 1000):
for c in range(b + 1, 1000):
if a + b + c == 1000 and is_triplet(a, b, c):
print a * b * c
exit(0)
```

I’ll have to rethink this, as it’s *really* inefficient. As it is, it runs in 18.034s!

**Updated:** take a look at another take at this problem and algorithm.

**Updated 2010/08/04:** Gustavo Niemeyer pointed an obvious optimization to the algorithm above (written in C)—the innermost loop is unnecessary. I rewrote it in Python to see the difference:

```
from sys import exit
def is_triplet(a, b, c):
return (a ** 2 + b ** 2 == c ** 2)
for a in range(1, 1000):
for b in range(a + 1, (1000 - a) / 2):
c = 1000 - a - b
if is_triplet(a, b, c):
print "%d * %d * %d = %d" % (a, b, c, a * b * c)
```

From 18s to 0.076s. As well, following Eduardo Habkost’s suggestion, I used psyco and execution time went down to 0.023s.