Project Euler Problem 9 Solution: Special Pythagorean triplet

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\lt b\lt c$ and $a^2 + b^2 = c^2$. These triples are commonly written as ($a$, $b$, $c$), and a typical example is $(3,\space 4,\space 5)$; $3^2 + 4^2 = 5^2$ 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\ge 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:

$$ \begin{split} a^2+b^2 &= c^2\\ a+b+c&=n\\ c&=n-a-b \end{split} $$

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$:

Solving for c

(1) Use our new definition for $c$

(2) Expand the right–hand side

(3) Isolate the $b$ terms on the left

(4) Factor both sides of the equation

(5) Solved for $b$ in terms of $a$ and $n$

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\lt b$ before the Pythagorean triangle check is faster.
We don’t need to confirm $b\lt c$ as $a^2 + b^2 = c^2$ already implies $b\lt 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

Solves all test cases for Hackerrank 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

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

Last Word

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