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

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

StackExchange Code Review Q#60652, answer score: 6