// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (11 votes, average: 5.00 out of 5)
Loading...

Project Euler Solutions

Project Euler 9 Solution

Project Euler 9 Solution

Project Euler 9: Find the only Pythagorean triplet, {a, b, c}, for which a + b + c = 1000


Project Euler 9 Problem Description

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.

Analysis

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 (gcd(a, b, c) = 1) and for any primitive Pythagorean triple, (ka, kb, kc) for any positive integer k is a non-primitive Pythagorean triple.

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.

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 r^2 = 2st is a square.
Then: a = r + s, b = r + t, 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 (when s and t are coprime) and non-primitive triplets, which are required to solve this problem.

We loop through the even r up to 550 to generate all the triplets necessary to solve different problems. In the case of triples having the same sum this method keeps the maximum product found.

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.

h_mark_sm-05bceb881aa02b72d688d21db01df5d8
This program and method
solves all test cases
on HackerRank

Project Euler 9 Solution

Runs < 0.001 seconds in Python 2.7.
download arrowUse this link to get the Project Euler 9 Solution Python 2.7 source.

Answer

Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.
|31875000|

Afterthoughts

  • This code was written to handle thousands of queries on a single run and is why we cache the results of triplet sums from 2 to 3000 in the pn dictionary.
  • Generating Pythagorean Triples
Project Euler 9 Solution last updated

Discussion

No comments yet.

Post a comment