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);
}
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?
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