Pythagorean triplet

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,  a2 + b2 = cFor example, 32 + 42 = 9 + 16 = 25 = 52. There exists exactly one Pythagorean triplet for which a + b + c = 1000.  Find the product abc.

Simple approach a2 + b2 = (N-a-b)2   => a+b+c =N   i.e., a<b<c, From the condition a < b < c, we conclude that
a <= (s − 3) /3 and   b < (s − a)/2.

Using a parametrization of Pythagorean triplets

A Pythagorean triplet (a, b, c) is by definition primitive if gcd(a, b, c) = 1. Since for Pythagorean triplets one has gcd(a, b) = gcd(b, c) = gcd(c, a), such a triplet is primitive if and only if gcd(a, b) = 1.

import java.util.Calendar;
public class Problem9 {

    //fast code- it good for intger = > produced 17 seconds
    public void PythagoreanPE() {
        long evalue =1000;
        long fv = 0;
        for (long i=3;i<=(evalue-3)/3;i++) {
            for (long j=i+1;j<=(evalue-1-i)/2;j++) {
                long k = evalue-i-j;
                if ((i*i+j*j)==(k*k)) {
                    System.out.println(i+ " - " + j + " - " + k + " - " );
                    fv= i*j*k;
                    System.out.println(fv);
                    break;
                }
            }
        }
    }

    //greatest common divisor
    public long gcd(long a, long b) {
       if (b==0) return a;
       return gcd(b,a%b);
    }

    //super fast code- it good for big integer = > produced 0 seconds
    public void PythagoreanPE1() {
        double s = 1000;
        double s2 = s / 2;
        double l = Math.sqrt(s2);
        for (int i =2;i< l;i++) {
            if (s2%i==0) {
                double sm = s2/i;
                while(sm%2==0){
                    sm=sm/2;
                }
                long k =0;
                if (i%2==1) 
                    k=i+2;
                else
                    k=i+1;
                while((k<2*i) && k<=sm) {
                    if (sm%k==0 && gcd(k,i)==1) {
                        double d = s2 /(k*i);
                        double n= k-i;
                        double a=d*(i*i-n*n);
                        double b=2*d*i*n;
                        double c=d*(i*i+n*n);
                        System.out.println(a+ " - " + b + " - " + c + " - " );
                        long fv= (long) (a*b*c);
                        System.out.println(fv);
                        break;
                    }
                    k=k+2;
                }
            }
        }
    }
    public static void main(String[] args) {
        long start = 0, end=0;

        Problem9 p = new Problem9();
        start =(Calendar.getInstance()).getTimeInMillis();
        p.PythagoreanPE();
        end =(Calendar.getInstance()).getTimeInMillis();
        System.out.println(start + " - " + end  + " - " +(end-start));

        System.out.println("");
        start =(Calendar.getInstance()).getTimeInMillis();
        p.PythagoreanPE1();
        end =(Calendar.getInstance()).getTimeInMillis();
        System.out.println(start + " - " + end  + " - " +(end-start));
    }
}
Advertisement

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: