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

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&amp;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

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

Answer 2

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 3

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

Answer 4

#include <stdio.h>

int main() // main always returns int!
{
 int a, b, c;
 for (a = 0; a<=1000; a++)
 {
  for (b = a + 1; b<=1000; b++) // no point starting from 0, otherwise you'll just try the same solution more than once. The condition says a < b < c.
  {
   for (c = b + 1; c<=1000; c++) // same, this ensures a < b < c.
   {
    if (((a*a + b*b == c*c) && ((a+b+c) ==1000))) // ^ is the bitwise xor operator, use multiplication for squaring
     printf("a=%d, b=%d, c=%d",a,b,c);
   }
  }
 }
 return 0;
}

Haven't tested this, but it should set you on the right track.

Answer 5

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 6

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 7

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 8

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<2x and n/2 is divisible by x*s
      y=s-x
      k=n/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 9

is there a mathematical solution of this problem ? I worked on it for a while but i still can't find the solution.

Any ideas?

Thanks

Answer 10

There is a quite dirty but quick solution to this problem. Given the two equation

a*a + b*b = c*c

a+b+c = 1000.

You can deduce the following relation

a = (1000*1000-2000*b)/(2000-2b)

since a must be an natural number. Hence you can:

for b in range(1, 500):
    if 1000*(500-b) % (1000-b) == 0:
        print b, 1000*(500-b) / (1000-b) 

Got result 200 and 375.

Good luck