Select Page

Project Euler 9 Problem Statement

A Pythagorean triplet is a set of three natural numbers, ab < 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

A Pythagorean triple consists of three positive integers a, b, and c, such that a2 + b2 = c2. These triples are commonly written as (a, b, c), and a typical example is (3, 4, 5); 32 + 42 = 52 or 9 + 16 = 25.

A primitive Pythagorean triple is one in which a, b and c are coprime (that is, gcd(a, b, c) = 1; they have no common factors between them) and for any primitive Pythagorean triple a non-primitive Pythagorean triple can be calculated as: (ka, kb, kc) for any positive integer k.

Solving this problem for one target sum: a + b + c = 1000 in this case, seemed a bit too trivial but solving for any target sum ≤ 3000 and running thousands of trials in a few milliseconds was a bit more challenging.

Dickson’s method

This solution uses Dickson’s method for generating Pythagorean triples. To find integer solutions to a2 + b2 = c2, find positive integers r, s, and t such that r2 = 2st is a square; then: a = r+s, b = r+t, and c = r+s+t.
From this we see that r is any even integer and that s and t are factors of \frac{r^2}{2}.
Example: Choose r = 6. Then \frac{r^2}{2}=18.
The three factor-pairs of 18 are: (1, 18), (2, 9), and (3, 6). All three factor pairs will produce triples using the above equations.

s = 1, t = 18 produces the triple [7, 24, 25] because x = 6+1 = 7, y = 6+18 = 24, z = 6+1+18 = 25.
s = 2, t = 9 produces the triple [8, 15, 17] because x = 6+2 = 8, y = 6+9 = 15, z = 6+2+9 = 17.
s = 3, t = 6 produces the triple [9, 12, 15] because x = 6+3 = 9, y = 6+6 = 12, z = 6+3+6 = 15. (Since s and t are not coprime, this triple is not primitive.)

This method finds both primitive triplets (when s and t are coprime) and non-primitive triplets.

Python program implementation

This solution will solve this and the HackerRank problem.
We loop through the even numbered r and add the triple’s product to a dictionary indexed on triple’s sum. In the case of triples having the same sum this method keeps the maximum product found. 550 was used as a limit to solve all the possible queries for sums less than or equal to 3000. This will solve this problem and all the hackerRank problems.

pn = {}
for r in range(2, 550, 2):
    st = r*r // 2
    for s, t in divisors(st):
        x = (r+s) + (r+t) + (r+s+t)
        pn[x] = (r+s) * (r+t) * (r+s+t)

For example, Pythagorean triples (15, 20, 25) and (10, 24, 26) both sum to 60, but their respective products are 7500 and 6240. We keep the maximum, 7500. This is achieved by using a dictionary and finding the products in ascending order.

HackerRank version

HackerRank Project Euler 9 increases the target sum from 1000 to 3000 and runs thousands of test cases. Additionally, when multiple triples have the same sum we are required to keep the maximum triple product. This solution solves this problem in a hundredth of a second.

Python 2.7 Source

Last Word

  • Pythagorean sums are always even.
  • This code handles thousands of queries on a single run by caching the results of triplet sums from 2 to 3000 in the pn dictionary.
  • Generating Pythagorean Triples