Project Euler #9 - Pythagorean triplets

This code works, and I'm trying to figure out if there's a better way to optimize it. As you can see, I've cut down drastically on time just by using numbers that work for a < b < c. Is there any outstanding thing that can reduce the time? It currently takes ~7 seconds.

Problem:

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

$$a^2 + b^2 = c^2$$

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

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

My code:

import time

start = time.time()

def pythag(a, b, c):
if a ** 2 + b ** 2 == c ** 2:
return True
return False

a = [x for x in range(1, 1000)]

for num in a:
for dig in range(num, 1000 - num):
for i in range(dig, 1000 - dig):
if num + dig + i == 1000:
if pythag(num, dig, i):
print(num, dig, i)
print("Product: {}".format(num * dig * i))
elapsed = time.time() - start
print("Time: {:.5f} seconds".format(elapsed))
exit(1)

# 200 375 425
# Product: 31875000
# Time: 7.63648 seconds
• You should take a look at Euclid's Formula, it will be very fast, you can find an explanation at en.wikipedia.org/wiki/Pythagorean_triple Aug 21 '14 at 1:01
• @clutton Just read through that. Thank you very much! Aug 21 '14 at 1:26
• With many of those Euler problems it is just finding the right way to go about it and sometimes the right formula will exist. You should get well under a second, good luck. :) Aug 21 '14 at 1:42
• Have you looked here codereview.stackexchange.com/questions/58548/…? This can be done with a single loop instead of 3. Aug 21 '14 at 22:09
• This problem can be solved using pencil and paper using Euklids formula. Aug 22 '14 at 5:48

Without changing your time too much I got these results:

Original run:

>>>
200 375 425
Product: 31875000
Time: 8.19322 seconds
>>>

New code:

>>>
200 375 425
Product: 31875000
Time: 0.28517 seconds
>>>

What I changed:

• I moved the timing to completely surround the code, instead of when it hit the triplet.
• I inlined the check for the triplet, as functions are slow in Python
• Instead of generating a list for num, I used a range object straight up to generate them as needed
• I eliminated the i loop and condition by using the fact that i will need to be 1000 - num - dig.

Resulting code:

import time

start = time.time()

for num in range(1, 1000):
for dig in range(num, 1000 - num):
i = 1000 - num - dig
if num * num + dig * dig == i * i
print(num, dig, i)
print("Product: {}".format(num * dig * i))

elapsed = time.time() - start
print("Time: {:.5f} seconds".format(elapsed))

Fun fact: the check for a triplet in this case can be reduced to:

num * dig + 1000 * i == 500000

Where did I get these magic numbers you ask? Math. Check it out:

$$(\text{num}+ \text{dig}+ i)^2 = 1000^2$$ Expand: $$\text{num}^2 + \text{dig}^2 + i^2 + 2 \; \text{num} \; \text{dig}+ 2 \; \text{num} \; i + 2 \; \text{dig} \; i = 1000000$$ Use triplet equality: $$2 i^2 + 2 \; \text{num} \; \text{dig}+ 2 \; \text{num} \; i + 2 \; \text{dig} \; i = 1000000$$

Factor:

$$i(\text{num}+ \text{dig}+ i) + \text{num} \; \text{dig}= 500000$$

Use fact that $\text{num}+ \text{dig}+ i = 1000$ in our case:

$$\text{num} \; \text{dig}+ 1000 i = 500000$$

• I like the inline version of triplet check. And yes, changing the i to limit it to the only possible value given num and dig greatly reduces the time (as seen in my latest edit). Thanks! Aug 21 '14 at 4:43
• Oops, forgot to show that I also did the same thing with removing the list. This is basically super close to the solution I came up with. Aug 21 '14 at 4:45
• Chose as answer just for that last part, reduces time to 0.115 seconds! Aug 21 '14 at 4:50

Naming and expressiveness

I found your code hard to read, due to issues with naming and general clumsiness in expression.

For example, your pythag() function should be

def is_pythagorean_triplet(a, b, c):
return a ** 2 + b ** 2 == c ** 2

Next, looking at if num + dig + i == 1000, I have to wonder, how did the a, b, and c in the original problem turn into weird variable names num, dig, and i?

for a in range(1, 1000):
for b in range(a, 1000 - a):
for c in range(b, 1000 - b):
if a + b + c == 1000:
if is_pythagorean_triple(a, b, c):
print(a, b, c)
print("Product: {}".format(a * b * c))
exit(0)

Now we have an inefficient brute-force solution, but at least it has the virtue of being a very literal translation of the problem into Python.

Note that exit(1) was not appropriate. By convention, a non-zero exit indicates an error.

Optimization

Without drastically changing the strategy, we can still make a major improvement. There is no point in iterating to find c such that a + b + c == 1000, when you can determine it by simple arithmetic.

for a in range(1, 1000):
for b in range(a, 1000 - a):
c = 1000 - a - b
if c < b:
break
if is_pythagorean_triple(a, b, c):
print(a, b, c)
print("Product: {}".format(a * b * c))
exit(0)
• Yes, the optimization you have mentioned has already been discussed and yields the same result. Nevertheless, I really appreciate a lot of the things you mentioned in the naming and expressiveness section because I am new to the language and all I've been using is a flake 8 lint for ST2. I should've added the beginner tag that I just learned is on this site (there isn't one on SO). Thank you! Aug 21 '14 at 8:17

Whilst for triples, it is easy to find the nice formula, in many problems that will not be so easy.

So, as it demonstrates a basic principle, you should have fewer loops and solve for terms where possible.

In this case, remove the loop over i and simply set i = 1000 - num - dig.

So in fact the extra constraint here is so useful, you may do not require the Euclid, but @clutton's comment suggests that you can use to it go much faster. Note that whilst I can't recall if I used the formula for this problem myself, I'm pretty sure I did find it essential for some other Euler problems.

• Yes, I noticed that (forgot to add to original post), and it reduced the time to 0.27 seconds. Aug 21 '14 at 4:37
• @Keith - I actually used Euclid's formula for the problem when I did it long ago and it solves in about 1ms which I thought was pretty fast compared to other methods I've seen. I wouldn't say that it is not a helpful formula for this particular problem. Aug 21 '14 at 16:48
• @clutton. Fair enough - I'll amend my comment. Aug 21 '14 at 21:48