Posts Tagged ‘special’

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