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

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

int main()
{
    const int sum = 1000;
    int a;
    for (a = 1; a <= sum/3; a++)
    {
        int b;
        for (b = a + 1; b <= sum/2; b++)
        {
            int c = sum - a - b;
            if ( a*a + b*b == c*c )
               printf("a=%d, b=%d, c=%d\n",a,b,c);
        }
    }
    return 0;
}

explanation:

• b = a;
  if a, b (a <= b) and c are the Pythagorean triplet,
  then b, a (b >= a) and c - also the solution, so we can search only one case
• c = 1000 - a - b; It's one of the conditions of the problem (we don't need to scan all possible 'c': just calculate it)

Answer 2

Here's a solution using Euclid's formula (link).

Let's do some math: In general, every solution will have the form

a=k(x²-y²)
b=2kxy
c=k(x²+y²)

where k, x and y are positive integers, y < x and gcd(x,y)=1 (We will ignore this condition, which will lead to additional solutions. Those can be discarded afterwards)

Now, a+b+c= kx²-ky²+2kxy+kx²+ky²=2kx²+2kxy = 2kx(x+y) = 1000

Divide by 2: kx(x+y) = 500

Now we set s=x+y: kxs = 500

Now we are looking for solutions of kxs=500, where k, x and s are integers and x < s < 2x. Since all of them divide 500, they can only take the values 1, 2, 4, 5, 10, 20, 25, 50, 100, 125, 250, 500. Some pseudocode to do this for arbitrary n (it and can be done by hand easily for n=1000)

If n is odd
  return "no solution"
else
  L = List of divisors of n/2
for x in L
  for s in L
    if x< s <2*x and n/2 is divisible by x*s
      y=s-x
      k=((n/2)/x)/s      
      add (k*(x*x-y*y),2*k*x*y,k*(x*x+y*y)) to list of solutions
sort the triples in the list of solutions
delete solutions appearing twice
return list of solutions

You can still improve this:

• x will never be bigger than the root of n/2
• the loop for s can start at x and stop after 2x has been passed (if the list is ordered)

For n = 1000, the program has to check six values for x and depending on the details of implementation up to one value for y. This will terminate before you release the button.

Answer 3

In C the ^ operator computes bitwise xor, not the power. Use x*x instead.

Answer 4

As others have mentioned you need to understand the ^ operator. Also your algorithm will produce multiple equivalent answers with the parameters a,b and c in different orders.

Answer 5

From man pow:

POW(3)                                       Linux Programmer's Manual                                      POW(3)

NAME
       pow, powf, powl - power functions

SYNOPSIS
       #include <math.h>

       double pow(double x, double y);
       float powf(float x, float y);
       long double powl(long double x, long double y);

       Link with -lm.

   Feature Test Macro Requirements for glibc (see feature_test_macros(7)):

       powf(), powl(): _BSD_SOURCE || _SVID_SOURCE || _XOPEN_SOURCE >= 600 || _ISOC99_SOURCE; or cc -std=c99

DESCRIPTION
       The pow() function returns the value of x raised to the power of y.

RETURN VALUE
       On success, these functions return the value of x to the power of y.

       If  x  is  a  finite  value less than 0, and y is a finite non-integer, a domain error occurs, and a NaN is
       returned.

       If the result overflows, a range error occurs, and the functions return HUGE_VAL, HUGE_VALF, or  HUGE_VALL,

as you see, pow is using floating point arithmetic, which is unlikely to give you the exact result (although in this case should be OK, as relatively small integers have an exact representation; but don't rely on that for general cases)... use n*n to square the numbers in integer arithmetic (also, in modern CPU's with powerful floating point units the throughput can be even higher in floating point, but converting from integer to floating point has a very high cost in number of CPU cycles, so if you're dealing with integers, try to stick to integer arithmetic).

some pseudocode to help you optimise a little bit your algorithm:

for a from 1 to 998:
    for b from 1 to 999-a:
        c = 1000 - a - b
        if a*a + b*b == c*c:
             print a, b, c

Answer 6

func maxProd(sum:Int)->Int{
    var prod = 0
    //    var b = 0
    var c = 0
    let bMin:Int = (sum/4)+1 //b can not be less than sum/4+1 as (a+b) must be greater than c as there will be no triangle if this condition is false and any pythagorus numbers can be represented by a triangle.
    for b in bMin..<sum/2 {
        for a in ((sum/2) - b + 1)..<sum/3{ //as (a+b)>c for a valid triangle
            c = sum - a - b
            let csquare = Int(pow(Double(a), 2) + pow(Double(b), 2))
            if(c*c == csquare){
                let newProd = a*b*c
                if(newProd > prod){
                    prod = newProd
                    print(a,b,c)
                }
            }
        }
    }
    //
    return prod
}

The answers above are good enough but missing one important piece of information a + b > c. ;)

More details will be provided to those who ask.