Project Euler Problem 9: Special Pythagorean Triplet

The source code for this problem can be found here.

Problem Statement

A Pythagorean triplet is a set of three natural numbers, \(a \lt b \lt 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 \(abc\).

Solution Discussion

Perform an exhaustive search over \(a,b,c\) using a few constraints to limit the search space.

\[\begin{split}&a \lt b \lt c \\ &a + b + c = 1000\end{split}\]

This is concisely achieved by iterating over the variable \(a\) first, then determining the range of variable \(b\) based on the current value of \(a\). Finally, the value of the variable \(c\) can be simply computed as:

\(c = 1000 - a - b\)

Solution Implementation

def solve():
    """ Compute the answer to Project Euler's problem #9 """
    triplet_sum = 1000
    min_a, max_a = 1, triplet_sum // 3
    for a in range(1, max_a):
        for b in range(a + 1, (triplet_sum - a) // 2):
            c = triplet_sum - a - b
            assert a < b < c, "constraint violated: {} < {} < {}".format(a, b, c)
            if a ** 2 + b ** 2 == c ** 2:
                return a * b * c  # there should only be one solution ...


expected_answer = 31875000

solutions.problem9.solve()

Compute the answer to Project Euler’s problem #9