# Solution to Problem 9 on Project Euler

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.

## My Solution

``````
#include <stdio.h>

int main(){
int a,b,c;
int ans=0;
for (a=1;a<500;a++){
for (b=1;b<500;b++){
for (c=1;c<500;c++){
if (a+b+c==1000){
if((a*a)+(b*b)==(c*c)){
ans=a*b*c;
break;
}
}
}
}
}

printf("%dn",ans);

}``````

## 2 thoughts on “Solution to Problem 9 on Project Euler”

1. Tanmay Chakrabarty

First thing is that, before finalizing the solution you should have checked the solution by flipping the loops, that is not from 1 to 500, but from 500 to 1. Secondly, as the a+b+c = 1000, thus when you have a & b, the c is always 1000 – (a+b), thus the third loop for c is also unnecessary. However, that was the solution I made but after submitting and going through the forum for getting more ideas, I saw people solved the problem just by math, no programming, those guys are genius.

However, I am one of your followers. Like to read your blog. Here is a comparison of the above mentioned 3 ways,

Loop through a,b,c from 1 to 500 need 31875000 loops.

Loop through a,b,c from 500 to 1 need 2812500 loops.

Looping only through a & b need 37500 loops.

Inspired from you, I will try to solve problem number 10, 11, 12

However, its a request that please don’t publish your solutions fully in public. You know it why, right?

2. tanzeel rana

eq 1 : a2 + b2 = c2

eq 2 : a + b + c = 1000

From eq 1 and eq 2 we can have

eq 3 : c = 1000 – a – b

Substitute the value of c from eq 3 into eq 1 we get :

eq 4 : a2 + b2 = (1000 – a – b)2

R.H.S of eq 4 is a trinomial squared. We know that square of a trinomial of such kind is

(a – b – c)2 = a2 + b2 + c2 – 2ab + 2bc – 2ca

We get :

a2 + b2 = 10002 + a2 + b2 – 2*1000*a + 2*a*b – 2*b*1000

Now we simplify to get a to the L.H.S

a = (10002 – 2*1000*b)/(2*1000*b)

Now I can use this to find out value of a where it is an integer and then use Math.sqrt( a*a + b*b ) to calculate the value of c. Then I can check if a+b+c==1000 holds to be true.

My solution :

public class ProjectEuler9 {

public static void main(String[] args) {
long start = System.nanoTime();

double a;

for(int b=1; b<1000; b++){

a = ( (Math.pow(1000, 2) – 2000*b ) / (2000- 2*b) );

if(Math.floor(a) == a) {
// a is an integer
double c = Math.sqrt((a*a + b*b));
System.out.println("a : " + a + " b :" + b + " c : " + c);
long product = (long) (a*b*c);
System.out.println("product abc : " + product);
break;

} else {
//a is not an integer.
}

}

long stop = System.nanoTime();
System.out.println("\nTime: " + (stop – start) / 1000 + " ns");

}

Output :

a : 375.0 b :200 c : 425.0
product abc : 31875000

Time: 3714 ns