A Pythagorean triplet is a set of three natural numbers, $a < b < c$, for which,

\begin{equation} a^2 + b^2 = c^2 \end{equation}

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

Remark

This is a fairly straighforward constraint satisfaction problem (CSP) and is perhaps most easily solved in a CSP modelling language such as MiniZinc. However, to employ such tools would be to defeat the very purpose of the exercise, which is to give us practice with implementation.

from six.moves import range, reduce

Version 1: The Obvious

pair_sum_eq = lambda n, start=0: ((i, n-i) for i in range(start, (n>>1)+1))

list(pair_sum_eq(21, 5))

[(5, 16), (6, 15), (7, 14), (8, 13), (9, 12), (10, 11)]

Note that $3a < a + b + c = 1000$, so $a < \frac{1000}{3} \Leftrightarrow a \leq \lfloor \frac{1000}{3} \rfloor = 333$ so $1 \leq a \leq 333$. Therefore, we need only iterate up to 333 in the outermost loop. Now, $b + c = 1000 - a$, so $667 \leq b + c \leq 999$, so we look at all pairs $333 \leq b < c$ such that $b + c = 1000 - a$ with the help of the function pair_sum_eq. Within the innermost loop, the $a, b, c$ now satisfy the constraints $a < b < c$ and $a + b + c = 1000$ so now we need only check that they indeed form a Pythagorean triplet, i.e. $a^2 + b^2 = c^2$, and yield it.

def pythagorean_triplet_sum_eq(n):
    for a in range(1, n//3+1):
        for b, c in pair_sum_eq(n-a, start=n//3):
            if a*a + b*b == c*c:
                yield a, b, c

list(pythagorean_triplet_sum_eq(1000))

[(200, 375, 425)]

prod = lambda iterable: reduce(lambda x,y: x*y, iterable)

prod(pythagorean_triplet_sum_eq(1000))

(200, 375, 425)

Version 2: Euclid's Formula

# TODO