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 and 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.

Having solved this problem for a target sum of 1000 was pretty easy, but HackerRank has us run thousands of test cases for any target sum ≤ 3000. 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 −1.
• Here’s the justification for using n//3:

  

• Checking the simpler a < b before the Pythagorean triangle check is faster.
• 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. Print −1 if none are found.

Python Source Code

1. n = int(input("The Pythagorean triplet that sums to "))
2. p = -1; trip = "None."
3. for a in range(n//3-1, 2, -1):
4. b = n*(n-2*a) // (2*(n-a))
5. c = n - a - b
6. if a<b and a*a + b*b == c*c: p = a*b*c; trip=(a,b,c); break
7. print ("is",trip," product =",p)

 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