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 &lt; b &lt; 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 &lt; b &lt; 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
Without changing your time too much I got these results:

Original run:

&gt;&gt;&gt; 
200 375 425
Product: 31875000
Time: 8.19322 seconds
&gt;&gt;&gt;


New code:

&gt;&gt;&gt; 
200 375 425
Product: 31875000
Time: 0.28517 seconds
&gt;&gt;&gt; 


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$$