Project Euler: Problem 9

After a short break because of Blogger being in read-only mode for quite a while, I'm back again, now with problem No. 9

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

a2 + b2 = c2

For example, 32 + 42 = 9 + 16 = 25 = 52.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

So, here we are, we have the sum and we know that a < b < c and on paper the sides would make a right-angled triangle. That gives us a + b > c as we can't have a triangle where the sum of the lenghts of two of its sides would be smaller than the length of the third one. For this case it means that c can't be bigger than 500, and as it is as well the biggest of the three numbers it also implies that neither a nor b can get bigger than 500. This means that we can set our upper limit to nr/2. As a < b it makes sense to start searching for b at a + 1. For each such pair of a and b we get c by substracting them from the target sum and if it works in the Pythagorean equation, we return it.

fn getTripleForSum nr =
    local half = nr/2
    local a, b, c

    for a = 1 to half do
        for b = (a + 1) to half do
            c = nr - a - b
            if c^2 == (a^2 + b^2) do
                return a*b*c

DISCLAIMER: All scripts and snippets are provided as is under Creative Commons Zero (public domain, no restrictions) license. The author and this blog cannot be held liable for any loss caused as a result of inaccuracy or error within these web pages. Use at your own risk.

This Post needs Your Comment!

Return to top