Solution to Problem 9 on Project Euler


The problem:

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?

    Reply
  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

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *