Special Pythagorean triplet: Project Euler Problem 9

Problem Statement:
A Pythagorean triplet is a set of three natural numbers, $a, 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 Idea:
We have 3 variables a,b,c. So, We need at least 3 equations to solve them in constant time. But, we are given 2 equations: $a+b+c=n$ and $c^2=a^2+b^2$. So, we combine these 2 equations and can get rid of c, $(n-a-b)^2=a^2+b^2$, which will simplify to $b={{n^2-2na}\over{2n-2a}}$. Now we can iterate through all possible values of a and find the solution in linear time.

Solution Gist:

Tagged: , , , , ,

5 thoughts on “Special Pythagorean triplet: Project Euler Problem 9”

1. Alumashka November 28, 2013 at 1:28 am Reply

However, with limitation “a + b + c = 1000” even O(N^2) solution would work less than a second.

It would be interesting extend the problem for far greater numbers…

2. Faisal R. November 28, 2013 at 6:54 am Reply

yes , for sure. 🙂

3. Alumashka at CodeAbbey November 30, 2013 at 5:28 am Reply

Hello, Faisal!

See, here it is:

The numbers there would be greater, over million, so that solution could be found only by your method, not by simply iterating over a and b… 🙂

Wouldn’t you mind mentioning you as a person who gives idea? If so, please check if your name is spelled correctly. Thanks a lot once more!

• Faisal R. December 1, 2013 at 9:20 pm Reply

I am honored, thank you 🙂

4. atiq September 30, 2014 at 8:42 pm Reply

Thank you Faisal…for very clean approach.