Project Euler Problem 9 Statement

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

For example,

.

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 a² + b² = c². These triples are commonly written as (a, b, c), and a typical example is (3, 4, 5); 3² + 4² = 5² 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>1.

Solving this problem for one target sum of 1000 seemed pretty easy, but HackerRank has us solve for any target sum ≤ 3000 and running thousands of trials in a few milliseconds. That was a bit more challenging.

An iterative approach

We are given the target sum, N, so this is our independent variable. It can assume any value, such as 1000 in this particular case. a, b, c are our dependent variables as we must somehow derive them through iteration. If we can reduce our iterative search to one independent variable and one dependent variable then this solution would yield an O(N) algorithm.

Well, c is easy – we can define it in terms of a, b and n as:

Now, with c out of the way, and through some algebraic magic, we can solve for b in terms of a and n. We only need one loop for a and can calculate b:

A few optimizations

• Looking downward from n//3 the first product (p) meeting the conditional’s criteria will be our maximum and we can break from the loop. If no solution is found then the value of p is left at −1.
• Here’s the justification for using n//3:

  

• Checking the simpler a < b before the Pythagorean triangle check is more efficient.
• We don’t need to confirm b < c as a² + b² = c² already implies b < c.
• Breaking out of the loop after the first (maximum) candidate is found saves 45% over similar solutions.

As expected, this algorithm worked to solve this problem and the HackerRank version within the time constraint.

HackerRank version

Extended to solve all test cases for Project Euler Problem 9

HackerRank requires us to run 3,000 test cases for 1 ≤ N ≤ 3000. As there could be more than one Pythagorean triplet that exists for the target sum, print the one with a maximum possible product of a, b and c. If none are found print −1.

Python Source Code

 Use this link to download the Project Euler Problem 9: Special Pythagorean triplet Python source.

 Run Project Euler Problem 9 using Python on repl.it

Last Word

• Pythagorean sums, a + b = c, are always even.
• Generating Pythagorean Triples