Project Euler Solution 9: Special Pythagorean triplet

This is part of the Project Euler series and about Problem 9: Special Pythagorean triplet, where one has to find a triplet of numbers satisfying the Pythagorean theorem and an additional condition.

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which a² + b² = c². For example, 32 + 42 = 9 + 16 = 25 = 52. There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.

There is a straightfoward way to just try all values for a, b, and c between 1 and 1000 and then check for both conditions:

def solution_brute_force() -> int:
    for a in range(1, 1000):
        for b in range(1, 1000):
            for c in range(1, 1000):
                if a + b + c == 1000 and a**2 + b**2 == c**2:
                    return a * b * c

If one does that, one gets the correct answer of 31,875,000, but it takes 11 s and is way too long.

It is easy to be a bit clever about this and just have two loops and compute c from a and b. Also we only try out the values for b which can make sense. We know that c > b > a, and c = 1000 - a - b, therefore it doesn't make sense to have b running further than 1000 - 2 a. This reduces the number of loop iterations from a billion to less than a million.

def solution_grid_search() -> int:
    for a in range(1, 1000):
        for b in range(a, 1000 - 2 * a):
            c = 1000 - a - b
            if a**2 + b**2 == c**2:
                return a * b * c

And therefore it is no surprise that this gets the solution in just 21 ms.