Clash Royale CLAN TAG#URR8PPP

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

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



19 Answers
19

#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=%dn",a,b,c);


return 0;



explanation:

a < b and b < c

for (b = a; b<=1000; b++)

a < b < c

b = a+1

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

^

a*a

^

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)

x < s < 2x

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:

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.

c = 1000-a-b;

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 equation

aa + bb = c*c

a+b+c = 1000.

You can deduce the following relation

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

or after two simple math transformation, 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.

c = 1000 - a - b;

From man pow:

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

pow

n*n

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.

x*x

a*a

pow

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

pow

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**

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



in C# it works great) However, sure it isn't the best way to calc))

using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication3

class Program

static void Main(string args)


double sum;
double vv=1000;

for (int i = 1; i <1001; i++)

for (int j = 1; j < 1001; j++)

for (int k = 1; k < 1001; k++)


if ((Math.Pow(i, 2) == Math.Pow(j, 2) + Math.Pow(k, 2)) && i+j+k == 1000)
Console.WriteLine(i + " " + j + " " + k + " = "+(i*j*k));
Console.ReadKey();












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.

Here's my code in javascript. It works fine.

function ptTriplet()

var a = 0, b = 0 , c = 1000;
for (var i = 0; i < 10000000; i++)
a = i;
c = 1000 - i;
for (var j = 0; j < c; j++)

c--;
b = 1000 - Math.abs(a) - Math.abs(c);

if(c < 0)
break;

if(a*a+b*b==c*c && a > 0 && b > 0)
return a +""+ b +""+ c;




#include <math.h>

#include <stdio.h>

int main()

const int sum = 1000;

int a;

for (a = 1; a < 1000; a++)

int b;

for(b = a + 1; b < 1000; b++)

int c = sum - a- b;



if ( (a+b+c == 1000) && (a*a + b*b== c*c) )

printf("a=%d, b=%d, c=%dn",a,b,c);







return 0;




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:

c=n-a-b

(a^2-(a-n)^2)/(2(a-n))

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

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.

here is the solution in c++.
easy to understand.

//Special Pythagorean triplet
#include<stdio.h>

int main()

int a=1,b=2,c=3,sum = 0;

for(a = 1; a <= 1000;a++)

for(b = 2; b <= 1000;b++)

for(c = 3; c <= 1000;c++)

if(a*a + b*b == c*c && a + b + c == 1000)

printf(" %d %d %d",a,b,c);
sum = a * b * c;
printf("n");
a++;
b++;
c++;




printf("Your product is : %dn",sum);
return 0;



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.

a+b+c = 1000

aˆ2 + bˆ2 = cˆ2

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

b=1000-a-c

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

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;




By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.