Finding pythagorean triplets for sum of sides

weiss

I'm trying some of the problems at projecteuler.net and 1 of the questions:

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,

a^2 + b^2 = c^2

For example: 3^2 + 4^2 = 9 + 16 = 25 = 5^2

There exists 1 pythagorean triplet for which a + b + c = 1000.
Find the product of abc.

Since these problems are intended to improve programming skills, i wrote this C++ routine..

[PHP]

for(double a(1);a < 1000;a++) {
for(double b(1);b < 1000;b++) {

double c = sqrt((a * a) + (b * b));

if(c + a + b == 1000) {
printf("\nPythogorean Triplet = [%0.f, %0.f, %0.f]",a,b,c);
printf("\nProduct = %0.f\n",a * b * c);
return 0;
}
}
}
return 0;
}
[/PHP]

output result of this:

Pythogorean Triplet = [200, 375, 425]
Product = 31875000

my question, is there a formula to solve this problem rather than using brute force routine incrementing a and b values?

like, if asked to get pythagorean triplets for the sum of a + b + c which is some aribitrary value (like in previous example 1000), is there elegant way to get results?

hope i'm making sense.

Fremen

There's a formula which generates all pythagorean triples. It should be on wikipedia. Generating all triples below a certain number and then checking if they summed to the number you want would definitely be faster than brute-forcing.

MathsManiac

That's a nice question. From your message, it seems this is curiosity rather than an assignment, so I'm assuming it's ok to give a solution.

All Pythagorean triples are generated by {m^2+n^2, m^2-n^2, 2mn}, where m and n are positive integers, and m>n.

You need a+b+c=1000, yielding m(m+n)=500. So, m and (m+n) are factors of 500.

m+n>m, so m(m+n)>m^2, so m<sqrt(500), and
m+n<2m (since m>n), so m(m+n)<2m^2, so m>sqrt(250).

The prime factorisation of 500 is 2.2.5.5.5, so the only factor of 500 between 15.8 and 22.4 is 20. Thus, m=20, n=5, giving the answer required: m^2+n^2 = 425; m^2-n^2 = 375; 2mn = 200.

Thomas_S_Hunterson

MathsManiac wrote: »

That's a nice question. From your message, it seems this is curiosity rather than an assignment, so I'm assuming it's ok to give a solution.

It's a problem off Project Euler IIRC.

weiss

Yes, it's a question from Euler project.
No, it's not assignment, just going through the problems in my own time.

Most of the user solutions were using method of brute force like mine..which isn't really "proper" way to solve it.

hivizman

I really like MathsManiac's elegant solution, but it's worth noting that, if {a, b, c} is a Pythagorean triplet, then so is {a*n, b*n, c*n} [= n*{a, b, c}] for any strictly positive integer n. The triplet {200, 375, 425} is 25 times the well-known Pythagorean triplet {8, 15, 17}, so if you were doing trial and error and noted that 8+15+17=40 is a factor of 1000, you could easily find the required triplet.

One other thing that MathsManiac's method shows is that, at least for a sum of 1000, the solution is unique. There must be integers that cannot be expressed as sums of Pythagorean triplets (clearly, as the smallest such triplet, {3, 4, 5}, sums to 12, then any integer less than 12 doesn't have a solution - I'm assuming that all numbers in a Pythagorean triplet must be strictly positive integers), but are there any integers that can be expressed as the sum of a Pythagorean triplet in more than one way? Actually, the answer is yes, for example, 60 can be expressed as the sum of {15, 20, 25} [=5*{3, 4, 5}] or as the sum of {10, 24, 26} = [2*{5, 12, 13}].

MathsManiac

And if anyone fancies exploring these further, it may be helpful to note that the triple will be "primitive" (i.e., not a multiple of another triple) if and only if m and n are coprime and not both odd.