Problem Description

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

For example, 3² + 4² = 9 + 16 = 25 = 5².

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

Analysis

This site provided a simple formula for generating Pythagorean triplets. Here’s the formula:
Suppose that m and n are two positive integers, with m < n.
Then n² – m², 2mn, and n² + m² is a Pythagorean triple.

Ok, let’s work this out:
(n² -m²) + 2mn + (n² + m²) = 1000
2n² + 2mn = 1000
2n(n+m) = 1000
n(n+m) = 500
for m=20, a
n² + mn = 500

So, to find the maximum n, such that m < n, we search downwards and return the first one found. An assumption for this method is that the gcd(a, b, c) = 1. This simply means that a, b and c need to be reduced to their lowest terms. For example, {6, 8, 10} is a Pythagorean triple, but can be reduced to {3, 4, 5}.

Solution

Runs < 1 second in Python.

def pe9(p):
  LL = int(p**.5)
  for i in range(1, LL, 2):
    for j in range(2, LL, 2):
        a = abs(j*j - i*i)
        b = 2*i*j;
        c = i*i + j*j
        if a+b+c == p:
           return a*b*c
print "Answer to PE9 = ",pe9(1000)

Comments