pythagorean triplet

[cool dude]

does anyone know of an easy algorithm (that i would understand) to get a pythagorean triplet. i know wat they are i just need an algorithm because wat i'm trying to do is find the pythagorean triplet where a + b + c = 1000. because i don't have an algorithm i'm doing guess and check. i tried making a program, but i think i'm doing something wrong so it doesn't work.

[cool dude]

well i just made a program and got the numbers. although i did it kind of forcefully so i still want to know the algorithm.

[Clayton]

well we know that the lowest pythagorean triplet is 3,4,5 right? so have a program come up with something to the effect of : (note this is in turing )

Turing:

%all this is doing is taking the three sides and checking if they are in ratio with the smallest whole pythagorean triplet fcn find_triplet (a,b,c:int) :boolean if a mod 3= 0 and b mod 4=5 and c mod 5 = 0 or a mod 4=0 and b mod 3 = 0 and c mod 5 =0 then     result true else     result false end if end find_triplet

something like that will allow you to input numbers to check and see if they are pythagorean triplets, or if you just want to find pythagorean triplets then

Turing:

type Pythagoreus     record :         a,b,c:int     end record fcn give_triplet (side:Pythagoreus, max:int) :Pythagoreus     for x:1..max         side.a:= x*3         side.b:= x*4         side.c:= x*5         result side     end for end give_triplet

(note the above code is untested) basically what it does is find all pythagorean triplets up to a specified number as for real numbers im not to sure of an algorithm to solve that ull just have to experiment

[Cervantes]

Here's what I would do:

Generate the first few unique pythagorean triplets. If your search is small enough, this may be done manually. The first two are: 3, 4, 5, and 5, 12, 13.

You can make a pythagorean triplet from one you already know simply by multiplying each value by a constant.

code:

a^2 + b^2 = c^2     // multiply both sides by 4 4(a^2 + b^2) = 4c^2 4a^2  + 4b^2 = 4c^2 (2a)^2 + (2b)^2 = (2c)^2

So take your first triplet: 3, 4, 5. Multiply it by 2 to get the new one: 6, 8, 10. Check if 6 + 8 + 10 == 1000. If not, move on to multiplying by 3 to get 9, 12, 15. Check. Once you get a sum that passes 1000, move on to the next triplet: 5, 12, 13. Repeat the process for this triplet.

Makes sense? Now we optimize it. We don't have to iterate through all the possibilities, multiplying the base triplet by 2 then by 3, etc. until we pass our target sum.

Our triplet is represented by a, b, c. We multiply each of a, b, and c by a natural number, k. Therefore, our terms are ka, kb, and kc, where k is a natural number

code:

ka + kb + kc = 1000     // For our first triplet: a, b, c = 3, 4, 5 k(3) + k(4) + k(5) = 1000 12k = 1000 k = 83.33333...

But we said k is a natural number. Therefore, there is no pythagorean triplet that is a multiple of the 3, 4, 5 triplet whose sum of a, b, and c equals 1000.

So, we move on to the next triplet: 5, 12, 13.

This also doesn't work. k = 33.333.... Try the next triplet. Repeat until you get it.

[Cervantes]

A quick search nailed it. The fourth triplet: 8, 15, 17.

code:

1000 / (8 + 15 + 17) = 25 .: triplet is a = 25(8), b = 25(15), c = 25(17)     a = 200, b = 375, c = 425 200 + 375 + 425 = 1000

[Andy]

for a small number like 1000, cervantes approach works very well, but what if it was 1351435890? then you'd need to generate a lot of pythagorean triples...

let a = (n/2 - b)/(1 - b/n) for where a and b are positive integers and n is the sum given by the question.

solve for b such that

for 1<b<n/2
(n^2)/(2n-2b) is an integer greater than 0

for your question, the code would be

code:

var n := 1000 for b : 1 .. round(n/4)     if abs (n*n/(2*n-2*b)) = round (n*n/(2*n-2*b)) then         var a: = (n/2 - b)/(1 - b/n)         put a, " ", b, " ", sqrt(a*a+b*b)                exit     end if end for

this solution runs in n time

[Andy]

akh.. or you can be smart and use plato's formula

(m^2+1)^2 = (m^2-1)^2 + (2m)^2

this will get your sum to be 2k(m^2+m) so

k(m^2+m)=500

so all you need to do is

code:

for m : 2 .. 100     if round (500 / (m * m + m)) = 500 / (m * m + m) then         put (m * m - 1) * (500 / (m * m + m))         put (2*m) * (500 / (m * m + m))         put (m * m + 1) * (500 / (m * m + m))     end if end for

[cool dude]

thanx. i actually did it a little differently. it's obviously less efficient but this was before i knew how to do it.

code:

var b : int := 0 var c : int := 0 for i : 1 .. 200     for a : 1 .. 1000         b := a + i         c := 1000 - b - a         if a ** 2 + b ** 2 = c ** 2 then             put a, " ", b, " ", c         end if     end for end for

its more brutal code but it works. although i really like Andys code with platos formula.

[Andy]

that would be the most obvious solution, it would run in n^2 time, very inefficient. simply arriving at the right should never be enough

[cool dude]

Andy wrote:

that would be the most obvious solution, it would run in n^2 time, very inefficient. simply arriving at the right should never be enough

i know thats why i asked how to do it. i still don't exactly understand how this algorithm works, and will it work for any triplet?

[rizzix]

hmm, i tried andy's method in haskell... i didn't get the right answer... infact it simply skips it... k*(2x, x*x-1, x*x+1) <-- that distribution is far too spread out.

[Andy]

oops, yeah rizzix is right.. but that solution still works for this question. my first solution works for all cases, but it runs in ntime, i'll see if i can optimize this further

[Andy]

code:

var n := 1000 for x : 1 .. ceil (sqrt (n))     for y : 1 .. x - 1         var k : real := (n / (2 * x * x + 2 * x * y))         if round (k) = k then             put 2 * x * y * k             put (x * x - y * y) * k             put (x * x + y * y) * k             return         end if     end for end for

this solution runs in n time, its based on the euclid's method of finding triplets

Given integers x and y,

A = x^2 - y^2
B = 2xy
C = x^2 + y^2

this is the fastest method i can come up with at the moment. if anyone knows an efficienty way of finding factors of a number, i can devise an multithreaded solution that will run in sqrt(n) time at worst.