Find Pythagorean triplet for which a + b + c = 100

Question

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which, a² + b² = c²

For example, 3² + 4² = 9 + 16 = 25 = 5².

There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.

Source: http://projecteuler.net/index.php?section=problems&id=9

I tried but didn't know where my code went wrong. Here's my code in C:

#include <math.h>
#include <stdio.h>
#include <conio.h>


void main()
{
    int a=0, b=0, c=0;
    int i;
    for (a = 0; a<=1000; a++)
    {
        for (b = 0; b<=1000; b++)
        {
            for (c = 0; c<=1000; c++)
            {
                if ((a^(2) + b^(2) == c^(2)) && ((a+b+c) ==1000)))
                    printf("a=%d, b=%d, c=%d",a,b,c);
            }
        }
    }
getch();    
}

Answer 1

for a in range(1,334):
    for b in range(500, a, -1):
        if a + b < 500:
            break
        c = 1000 - a - b
        if a**2 + b**2 == c**2:
            print(a,b,c)

Further optimization from Oleg's answer. One side cannot be greater than the sum of the other two. So a + b cannot be less than 500.

Answer 2

While as many people have pointed out that your code will work fine once you switch to using pow. If your interested in learning a bit of math theory as it applies to CS, I would recommend trying to implementing a more effient version using "Euclid's formula" for generating Pythagorean triples (link).

Answer 3

I know this question is quite old, and everyone has been posting solutions with 3 for loops, which is not needed. I got this solved in O(n), by **equating the formulas**; **a+b+c=1000 and a^2 + b^2 = c^2**

So, solving further we get;

a+b = 1000-c

(a+b)^2 = (1000-c)^2

If we solve further we deduce it to;

a=((50000-(1000*b))/(1000-b)). We loop for "b", and find "a".

Once we have "a" and "b", we get "c".

public long pythagorasTriplet(){
    long a = 0, b=0 , c=0;

    for(long divisor=1; divisor<1000; divisor++){
        if( ((500000-(1000*divisor))%(1000-divisor)) ==0){
            a = (500000 - (1000*divisor))/(1000-divisor);
            b = divisor;
            c = (long)Math.sqrt(a*a + b*b);
            System.out.println("a is " + a + " b is: " + b + " c is : " + c);
            break;
        }
    }
    return a*b*c;
}

Answer 4

I'm afraid ^ doesn't do what you think it does in C. Your best bet is to use a*a for integer squares.

Answer 5

I think the best approach here is this:

int n = 1000;
unsigned long long b =0;
unsigned long long c =0;
for(int a =1;a<n/3;a++){
    b=((a*a)- (a-n)*(a-n)) /(2*(a-n));
    c=n-a-b;

    if(a*a+b*b==c*c)
        cout<<a<<' '<<b<<' '<<c<<endl;
 }

explanation: We shall refer to the N and A constant so we will not have to use two loops. We can do it because c=n-a-b and b=(a^2-(a-n)^2)/(2(a-n)) I got these formulas by solving a system of equations:

a+b+c=n, a^2+b^2=c^2

Answer 6

As mentioned above, ^ is bitwise xor, not power.

You can also remove the third loop, and instead use c = 1000-a-b; and optimize this a little.

Pseudocode

for a in 1..1000
    for b in a+1..1000
        c=1000-a-b
        print a, b, c if a*a+b*b=c*c