Problem 9 - Special Pythagorean Triplets

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 a*b*c.

This is a fairly straightforward problem, for which we can use optimizations that we've previously used: searching high-to-low; and limiting our search space.

answer = 0
for c in range(1000,3,-1):
    for b in range(c-1,2,-1):
        a = 1000 - (c + b)
        if c**2 == (a**2 + b**2) and c:
            answer = a*b*c

# 0.368048191071 seconds

From this implementation, we can improve a fair bit. It already searches high-to-low, but we can limit the size of the number space that it searches with a little math. Since our initial search space is across the value of c (the hypotenuse in our Pythagorean triple), we can reduce its size from 1000 to 500, since the smallest factor that can be part of a Pythagorean triple is 2 (Maths here)

answer = 0
for c in range(500,2,-1):
    if answer != 0:
        break
    for b in range(c-1,2,-1):
        a = 1000 - (c + b)
        if c**2 == (a**2 + b**2):
            answer = a*b*c
            break

Here, we also add break conditions for when the answer is found, so that we don't keep searching once our answer is found, dropping our time to:

# 0.0235221385956 seconds

For this method, this is about as optimal as possible without diving deeper into the mathematical properties of Pythagorean triangles.