Project Euler Problem 9 Solution

Project Euler Problem 9 Solution

Special Pythagorean triplet
by {BetaProjects} | MAY 9, 2009 | Project Euler

Project Euler Problem 9 Statement

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

Solving for c

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 a 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

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

HackerRank version

HackerRank requires us to run 3000 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

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