Project Euler Problem 9: Special Pythagorean triplet

A Pythagorean triplet is a set of three natural numbers, $a

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

In [1]:
from six.moves import range, reduce

Version 1: The Obvious

In [2]:
pair_sum_eq = lambda n, start=0: ((i, n-i) for i in range(start, (n>>1)+1))
In [3]:
list(pair_sum_eq(21, 5))
Out[3]:
[(5, 16), (6, 15), (7, 14), (8, 13), (9, 12), (10, 11)]

Note that $3a pair_sum_eq. Within the innermost loop, the $a, b, c$ now satisfy the constraints $a

In [4]:
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
In [5]:
list(pythagorean_triplet_sum_eq(1000))
Out[5]:
[(200, 375, 425)]
In [6]:
prod = lambda iterable: reduce(lambda x,y: x*y, iterable)
In [7]:
prod(pythagorean_triplet_sum_eq(1000))
Out[7]:
(200, 375, 425)

Version 2: Euclid's Formula

In [8]:
# TODO

Comments

Comments powered by Disqus