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

https://stackoverflow.com/questions/2817848

26-09-2019
|

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();    
}

Solution

#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)

OTHER TIPS

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

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.

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

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

a*a + b*b = c*c

a+b+c = 1000.

You can deduce the following relation

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

or after two simple math transformations, you get:

a = 1000*(500-b) / (1000 - b)

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

#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.

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

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

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.

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).

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;
}

Euclid method gives the perimeter to be m(m+n)= p/2 where m> n and the sides are m^2+n^2 is the hypotenuse and the legs are 2mn and m^2-n^2.thus m(m+n)=500 quickly gives m= 20 and n=5. The sides are 200, 375 and 425. Use Euclid to solve all pythorean primitive questions.

As there are two equations (a+b+c = 1000 && aˆ2 + bˆ2 = cˆ2) with three variables, we can solve it in linear time by just looping through all possible values of one variable, and then we can solve the other 2 variables in constant time.

From the first formula, we get b=1000-a-c, and if we replace b in 2nd formula with this, we get c^2 = aˆ2 + (1000-a-c)ˆ2, which simplifies to c=(aˆ2 + 500000 - 1000a)/(1000-a).

Then we loop through all possible values of a, solve c and b with the above formulas, and if the conditions are satisfied we have found our triplet.

    int n = 1000;

    for (int a = 1; a < n; a++) {
        int c = (a*a + 500000 - 1000*a) / (1000 - a);
        int b = (1000 - a - c);

        if (b > a && c > b && (a * a + b * b) == c * c) {
            return a * b * c;
        }
    }

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

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.

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.

Licensed under: CC-BY-SA with attribution

Not affiliated with StackOverflow