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

67,413

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

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

Solution 3

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.

Solution 4

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

Solution 5

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

Share:
67,413
r18ul
Author by

r18ul

I'm partly truth, partly fiction.

Updated on October 18, 2020

Comments

  • r18ul
    r18ul over 3 years

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

    For example, 32 + 42 = 9 + 16 = 25 = 52.

    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();    
    }
    
  • T .
    T . almost 14 years
    Actually, since it's to the power of 2 and we're dealing with integers, seems to me a*a, etc. is easier.
  • fortran
    fortran almost 14 years
    Don't advise to use pow, because it will yield imprecise results, as I have commented my answer
  • Amarghosh
    Amarghosh almost 14 years
    how about eliminating the third loop by putting c = 1000 - a - b; That way you don't need to check for 1000 in the if condition. runs faster.
  • sharptooth
    sharptooth almost 14 years
    Very true about multiple answers.
  • JeremyP
    JeremyP almost 14 years
    Start a from 1. Apart from a = 0 => a degenerate triangle, there are obviously no solutions such that bb = cc and b < c.
  • IVlad
    IVlad almost 14 years
    There are many optimizations of course. This can even be solved relatively easy with no programming at all. I think it's important to understand this trivial solution before seeking to optimise it though.
  • r18ul
    r18ul almost 14 years
    Dude can you explain me the logic: a=1 Ok; But b=a & c=1000-a-b ? Can you please elaborate. Thanks
  • Oleg Razgulyaev
    Oleg Razgulyaev almost 14 years
    @Rahul: I've added few lines of explanation
  • Pete Kirkham
    Pete Kirkham almost 14 years
    And with automatic truncation to integers, I've even seen use use of ^ to 'square' floating point values.
  • r18ul
    r18ul almost 14 years
    @ oraz: Thanks dude. I got it
  • user unknown
    user unknown almost 14 years
    If a < b and b < c, a can't be greater/equals than 1000/3 and b can't be greater/equals than 1000/2. And since a, b, c aren't used outside their loops, just declare them in the for-head.
  • Ponkadoodle
    Ponkadoodle almost 14 years
    "for (b = a; b<=1000; b++)" - part of the problem description is that a < b < c so b cannot be equal to a. Make that b = a+1
  • CY5
    CY5 about 9 years
    1 up-vote for dirt, but I feel sad when I compare it with my wasted hour with this question :-||
  • gcoulby
    gcoulby over 8 years
    When do you get the 500000 from in this instance?
  • Baradwaj Aryasomayajula
    Baradwaj Aryasomayajula over 8 years
    @gcoulby In the above program, he considered n=1000... so it must be 50000 not 500000... He must be mistaken...
  • PapaDiHatti
    PapaDiHatti almost 6 years
    a<b<c so first loop should go till < sum/3 not <=sum/3