Problem 9 - Special Pythagorean Triplet

Problem

This problem comes from Project Euler 9

Problem

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 $a \times b \times c$

Solution

In order to generate Pythagorean Triples we can use Euclid’s Formula, where $a, b, c$ in the Pythagorean Theorem are

And $m$ and $n$ are arbitrary integers where $m > n > 0$ .

Now, we could go forward as is and write the following code

for n in range (1, 1000):
    for m in range(n+1, 1000):
        a = m**2 - n**2
        b = 2*m*n
        c = m**2 + n**2

        if (a+b+c == 1000):
            print(a*b*c)
            break

And it would work fine! But we can make an optimization. We know that we are aiming for

So why not perform some simplications? Substituting in Euclid’s Formula we get

And simplifying the above equation

Finding when $m(m+n) = 500$ and then calculating $a$, $b$, and $c$ is less computationally expensive and faster than the code shown above.

Code

# Project Euler: Problem 9
# Special Pythagorean Triplet

# Euclid's Formula is used here. 
# Check out https://en.wikipedia.org/wiki/Pythagorean_triple

for n in range (1, 500):
    for m in range(n+1, 500):
        if (m*(m+n) == 500):
            a = m**2 - n**2
            b = 2*m*n
            c = m**2 + n**2

            print(a*b*c)
            break

// Project Euler: Problem 9
// Special Pythagorean Triplet
// Alternate Rust version

fn main() {
    'outer: for n in 1_i32..=500 {
        for m in (n+1)..=500 {
            if m*(m+n) == 500 {
                let a: i32 = m.pow(2) - n.pow(2);
                let b: i32 = 2*m*n;
                let c: i32 = m.pow(2) + n.pow(2);

                println!("{}", a*b*c);
                break 'outer;
            }
        }
    }
}