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 straightforward 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$. We can combine these into $1000 - a - b > b$, add $b$ on both sides and have $1000 - a > 2 b$. Dividing by 2 gives us $500 - a/2 > b$. Therefore it doesn't make sense to have b running further than $500 - a/2$. 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, 500 - a // 2):
            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.