Computer Science Canada

pythagorean triplet
Author:  cool dude [ Fri Jun 16, 2006 5:20 pm ]
Post subject:  pythagorean triplet
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.
Author:  cool dude [ Fri Jun 16, 2006 6:28 pm ]
Post subject: 
well i just made a program and got the numbers. Smile although i did it kind of forcefully so i still want to know the algorithm.
Author:  Clayton [ Fri Jun 16, 2006 6:33 pm ]
Post subject: 
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 Sad)
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 Sad ull just have to experiment
Author:  Cervantes [ Fri Jun 16, 2006 6:41 pm ]
Post subject: 
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.
Author:  Cervantes [ Fri Jun 16, 2006 6:49 pm ]
Post subject: 
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
Author:  Andy [ Fri Jun 16, 2006 7:44 pm ]
Post subject: 
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
Author:  Andy [ Fri Jun 16, 2006 8:24 pm ]
Post subject: 
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
Author:  cool dude [ Fri Jun 16, 2006 9:01 pm ]
Post subject: 
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.
Author:  Andy [ Sat Jun 17, 2006 1:33 am ]
Post subject: 
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
Author:  cool dude [ Sat Jun 17, 2006 9:01 am ]
Post subject: 
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?
Author:  rizzix [ Sat Jun 17, 2006 11:24 am ]
Post subject: 
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.
Author:  Andy [ Sat Jun 17, 2006 2:10 pm ]
Post subject: 
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
Author:  Andy [ Sat Jun 17, 2006 3:20 pm ]
Post subject: 
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.

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy