Special Pythagorean triplet (problem 9)

Posted: 01/07/2013 in Project Euler
Tags: , , ,

Problem 9 of PE’s website says:

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$

First of all, after you submit the correct answer on that website, a new forum is enabled to you so that you can post there the way you reached your solution, and there I found an elegant method that does not require code. I will just quote it:

@theopigott:
"I decided to have a go at this one on paper.
I considered Euclid's formula for generating triples (a,b,c):
a = m^2 - n^2, b = 2mn, c = m^2 + n^2.

The aim is that a + b + c = 1000
This implies that 2m^2 + 2mn = 1000, so m^2 + mn = m(m + n) = 500.
Now 500 = 2^2 * 3^3, so the possible factorisations (values for m and (m+n)) are:
1 * 500
2 * 250
4 * 125
5 * 100
10 * 50
20 * 25

However m > n and (m+n) > m, so the only one that would work is m = 20 and m + n = 25, giving n = 5.
Substituting back into Euclid's formula gives a = 375, b = 200, c = 425, and the desired product abc = 31875000."

Isn’t that beautiful? 😀 Before of writing my C program to solve the problem, I also tried to do it by hand through Euclid’s formula, but I got stuck at $m(m + n) = 500$. There I had an equation with two variables, so I couldn’t continue (avoiding trial and error). I also tried to solve the system of equations

$a + b + c = 1000 \\ a^{2} + b^{2} = c^{2}$

and performing the change of variables $a=m^2 - n^2$ , $b=2mn$ , $c=m^2+n^2$ (because then I could have a system of two equations with only two variables), but then I got a more complex equation with square roots and everything, so it didn't help to simplify the problem, but right the opposite.

I didn't thought about factorizing 500… shame on me! So instead I wrote the following program that solves the problem by brute force:

#include <stdio.h>
#include <stdlib.h>

double exponenciar (double base, int exponent);
/* Returns the result of (base ^ exponent) */

int findProduct (int sum_numbers);
/* Returns a number a*b*C such that (a, b, c) is a Pythagorean triplet and
a + b + c = sum_number */

double exponenciar (double base, int exponent){

double retorna;

if (exponent == 0){
retorna = 1;
} else {
retorna = base * exponenciar (base, exponent - 1);
}

return retorna;
}

int findProduct (int sum_numbers){

int a = 3, b = 4, c = sum_numbers - a - b;
int square_a = (int) exponenciar (a, 2);
int square_b = (int) exponenciar (b, 2);
int square_c = square_a + square_b;

int result = 0;

for (b = 4; b < sum_numbers; b++){
square_b = (int) exponenciar (b, 2);
for (a = 3; a < sum_numbers; a++){
square_a = (int) exponenciar (a, 2);
square_c = square_a + square_b;
c = 1000 - a - b;

if ((int) exponenciar (a + b + c, 2) == (int) exponenciar (sum_numbers, 2) &&
square_c == (int) exponenciar (c, 2)){
result = a*b*c;
break;
}
}
}

return result;
}

int main (int argc, char *argv[]){

int number = atoi (argv[1]);

printf ("%d\n", findProduct (number));

return 0;
}

Time to compile and to run the program:

\$ (gcc -Wall -Wconversion prob9.c) && ./a.out 1000
31875000