Re: pythagorean triples exercise
"Tim Roberts" wrote in message news:5na7c6dlv0qii3pta58as50lmjcrrtk...@4ax.com... Baba wrote: a^a + b^b = c^c is the condition to satisfy No, it's not. It's a^2 + b^2 = c^2, where a, b, and c are integers. Perhaps you meant a*a + b*b = c*c. Or possibly a**2 + b**2 = c**2 and i need to use loops and "n" will be an upper limit of one (or more?) of the loops but i am a bit lost. Please help me get thinking about this right. The simplest (but not most efficient) method is brute force, using three loops, one each for a, b, and c. You can compute the largest "c" you will need by computing the square root of a*a+b*b. If square roots have to be used, you might as well use the two-loop algorithm, as you're nearly there. A simpler estimate for the largest c is just a+b, although it might involve a few extra iterations. -- Bartc -- http://mail.python.org/mailman/listinfo/python-list
Re: pythagorean triples exercise
Baba wrote: > >i need a hint regarding the following exercise question: > >"Write a program that generates all Pythagorean triples whose small >sides are no larger than n. >Try it with n <= 200." > >what is "n" ? i am guessing that it is a way to give a bound to the >triples to be returned but i can't figure out where to fit in "n". Yes. That's saying your program should read a value for N, check that N is not larger then 200, then generate the Pythagorean triples where A and B are less than N. >a^a + b^b = c^c is the condition to satisfy No, it's not. It's a^2 + b^2 = c^2, where a, b, and c are integers. Perhaps you meant a*a + b*b = c*c. >and i need to use loops >and "n" will be an upper limit of one (or more?) of the loops but i am >a bit lost. Please help me get thinking about this right. The simplest (but not most efficient) method is brute force, using three loops, one each for a, b, and c. You can compute the largest "c" you will need by computing the square root of a*a+b*b. -- Tim Roberts, t...@probo.com Providenza & Boekelheide, Inc. -- http://mail.python.org/mailman/listinfo/python-list
Re: pythagorean triples exercise
On 10/23/2010 3:34 AM, Lawrence D'Oliveiro wrote: In message<8idui6f21...@mid.individual.net>, Peter Pearson wrote: Is it important to let "a" range all the way up to b, instead of stopping at b-1? (tongue in cheek) Makes no difference. :) The difference is that before one writes the restricted range, one must stop and think of the proof that a==b is not possible for a pythagorean triple a,b,c. (If a==b, c==sqrt(2)*a and the irrationality of sqrt(2) implies that c is also irrational and therefore not integral). The OP asked for how to translate the problem description into two loops, one nested inside the other, and I gave the simplest, obviously correct, brute-force search answer. If the problem specification had asked for primitive triples (no common factors), an additional filter would be required. Another respondent referred, I believe, to Euclid's formula https://secure.wikimedia.org/wikipedia/en/wiki/Pythagorean_triple However, it is not well suited to the problem specified. -- Terry Jan Reedy -- http://mail.python.org/mailman/listinfo/python-list
Re: pythagorean triples exercise
In message <8idui6f21...@mid.individual.net>, Peter Pearson wrote: > Is it important to let "a" range all the way up to b, instead of > stopping at b-1? (tongue in cheek) Makes no difference. :) -- http://mail.python.org/mailman/listinfo/python-list
Re: pythagorean triples exercise
In message , Baba wrote: > csqrt = math.sqrt(csqrd) > for c in range (1, csqrd): > if c * c == a * a + b * b and math.floor(csqrt) == csqrt: > print (a,b,c) Is there such a term as “bogosearch”? -- http://mail.python.org/mailman/listinfo/python-list
Re: pythagorean triples exercise
As I indicated, generating such triples is easy. What you found is the edge case that 2*i*j = 200 => 100 = i*j so (i,j) = (100,1) or (50,2) (25,4), (20,5) or (10,10). The maximal value are i = 100, j = 1. The other sides are i^2 - j^2 = 10,000 - 1 = i^2 + j^2 = 10,000 + 1 = 10,001 ...and there you have your figures. A real proof consists of a bit more, but nobody wants to read it and there is no easy way to notate it in plain text. - Original Message - From: "Mel" To: python-list@python.org Sent: Friday, October 22, 2010 2:20:47 PM Subject: Re: pythagorean triples exercise MRAB wrote: > On 22/10/2010 13:33, Baba wrote: >> only a has an upper limit of 200 >> > Really? The quote you gave included "whose small sides are no larger > than n". Note: "sides", plural. Strangely, there does seem to be a limit. Fixing one side at 200, the largest pythagorean triple I have found is (200, , 10001.0). So far my math has not been up to explaining why. Mel -- http://mail.python.org/mailman/listinfo/python-list -- http://mail.python.org/mailman/listinfo/python-list
Re: pythagorean triples exercise
Mel wrote: > MRAB wrote: >> On 22/10/2010 13:33, Baba wrote: > >>> only a has an upper limit of 200 >>> >> Really? The quote you gave included "whose small sides are no larger >> than n". Note: "sides", plural. > > Strangely, there does seem to be a limit. Fixing one side at 200, the > largest pythagorean triple I have found is (200, , 10001.0). So far > my math has not been up to explaining why. Of course. Sorry. The difference between 10001**2 and 10002**2 exceeds 200**2. So adding a**2 can never even get as far as the next integral square. Mel. -- http://mail.python.org/mailman/listinfo/python-list
Re: pythagorean triples exercise
MRAB wrote: > On 22/10/2010 13:33, Baba wrote: >> only a has an upper limit of 200 >> > Really? The quote you gave included "whose small sides are no larger > than n". Note: "sides", plural. Strangely, there does seem to be a limit. Fixing one side at 200, the largest pythagorean triple I have found is (200, , 10001.0). So far my math has not been up to explaining why. Mel -- http://mail.python.org/mailman/listinfo/python-list
Re: pythagorean triples exercise
On 22/10/2010 13:33, Baba wrote: On Oct 22, 8:07 am, Dennis Lee Bieber wrote: On Thu, 21 Oct 2010 03:51:07 -0700 (PDT), Baba declaimed the following in gmane.comp.python.general: Hi everyone i need a hint regarding the following exercise question: "Write a program that generates all Pythagorean triples whose small sides are no larger than n. Try it with n<= 200." what is "n" ? i am guessing that it is a way to give a bound to the triples to be returned but i can't figure out where to fit in "n". a^a + b^b = c^c is the condition to satisfy and i need to use loops Well, I'd interpret it to mean that a<= 200 AND b<= 200 since c is the hypotenuse, which by definition is longer than either of the sides. The brute force approach is a nested set of "for" loops, running 1-200 (remember that (x)range(200) runs 0-199). The alternative is to study the information at http://www.math.uic.edu/~fields/puzzle/triples.html and filtering out entries where the first two components are>200... Looking at the middle term "2*m*n" would have to be less than 201, and the first term "n*n-m*m"< 201 In Python, this can all be done in a one-liner... [(n*n - m*m, 2*m*n, n*n + m*m) for n in xrange(2,101) for m in xrange(1,n) if 2*m*n< 201 and n*n-m*m< 201] Converting this to a clean set of nested loops and nice lines of output is a different matter. Oh, and DO study the link I gave so you can cite it when you turn in this intriguing formulation... after all, no need for math.sqrt -- Wulfraed Dennis Lee Bieber AF6VN wlfr...@ix.netcom.comHTTP://wlfraed.home.netcom.com/ Hi Wulfraed, only a has an upper limit of 200 Really? The quote you gave included "whose small sides are no larger than n". Note: "sides", plural. the program needs to output the following triple for a == 200: (200 , 609,641) so at this stage my problem is: how to set the upper limit for b in a smart way? My solution below is not efficient i believe. import math for a in range (190,200): for b in range (a,a*a): csqrd = a * a + b * b csqrt = math.sqrt(csqrd) for c in range (1, csqrd): if c * c == a * a + b * b and math.floor(csqrt) == csqrt: print (a,b,c) -- http://mail.python.org/mailman/listinfo/python-list
Re: pythagorean triples exercise
On Fri, 22 Oct 2010 01:35:11 -0400, Terry Reedy wrote: > On 10/21/2010 7:55 PM, Baba wrote: > >> the bit i'm having difficulties with in constructing my loops is: >> "whose small sides are no larger than n" > > from math import sqrt > > def py_trips(n): >for b in range(4,n+1): > for a in range(3,b+1): >cf = sqrt(a*a+b*b) >c = int(cf) >if c == cf: yield a, b, c [snip] Is it important to let "a" range all the way up to b, instead of stopping at b-1? (tongue in cheek) -- To email me, substitute nowhere->spamcop, invalid->net. -- http://mail.python.org/mailman/listinfo/python-list
Re: pythagorean triples exercise
On Oct 22, 6:35 am, Terry Reedy wrote: > On 10/21/2010 7:55 PM, Baba wrote: > > > the bit i'm having difficulties with in constructing my loops is: > > "whose small sides are no larger than n" > > from math import sqrt > > def py_trips(n): > for b in range(4,n+1): > for a in range(3,b+1): > cf = sqrt(a*a+b*b) > c = int(cf) > if c == cf: yield a, b, c > > for t in py_trips(200): print(t) > > # prints > (3,4,5) > ... > (150, 200, 250) > > This version assumes that if a*a+b*c is an exact square of an integer, > the floating point sqrt will be an exact integral value, which I believe > it should be for values up to the max (for n max 200) of 8. > > It produces multiples of each triple, such as (3,4,5), (6,8,10), > (9,12,15), ... (150,200, 250), which a different formulation of the > problem might exclude, to only ask for 'basic' triples of relatively > prime numbers. > > -- > Terry Jan Reedy Hi All, Only 'a' has an upper limit of 200. The exercise is not clar about that maybe but assuming i am correct my program would need to be able to generate the following triple: (200 ,609,641 ) My code below does that now but i think the way i compute b's upper limit is not efficient. import math for a in range (1,200): for b in range (a, a * a): csqrd = a * a + b * b c = math.sqrt(csqrd) if math.floor(c) == c: print (a,b,int(c)) thanks Baba -- http://mail.python.org/mailman/listinfo/python-list
Re: pythagorean triples exercise
On Oct 22, 6:35 am, Terry Reedy wrote: > On 10/21/2010 7:55 PM, Baba wrote: > > > the bit i'm having difficulties with in constructing my loops is: > > "whose small sides are no larger than n" > > from math import sqrt > > def py_trips(n): > for b in range(4,n+1): > for a in range(3,b+1): > cf = sqrt(a*a+b*b) > c = int(cf) > if c == cf: yield a, b, c > > for t in py_trips(200): print(t) > > # prints > (3,4,5) > ... > (150, 200, 250) > > This version assumes that if a*a+b*c is an exact square of an integer, > the floating point sqrt will be an exact integral value, which I believe > it should be for values up to the max (for n max 200) of 8. > > It produces multiples of each triple, such as (3,4,5), (6,8,10), > (9,12,15), ... (150,200, 250), which a different formulation of the > problem might exclude, to only ask for 'basic' triples of relatively > prime numbers. > > -- > Terry Jan Reedy Hi Terry Only a has an upper limit of 200. The exercise is n ot clar about that i agree but assuming i am correct my program would need to be able to generate the following triple: (200 ,609,641 ) My code below does that now but i think the way i compute b's upper limit is not efficient. import math for a in range (1,200): for b in range (a,200): csqrd = a * a + b * b c = math.sqrt(csqrd) if math.floor(c) == c: print (a,b,int(c)) thanks Baba -- http://mail.python.org/mailman/listinfo/python-list
Re: pythagorean triples exercise
On Oct 22, 8:07 am, Dennis Lee Bieber wrote: > On Thu, 21 Oct 2010 03:51:07 -0700 (PDT), Baba > declaimed the following in gmane.comp.python.general: > > > Hi everyone > > > i need a hint regarding the following exercise question: > > > "Write a program that generates all Pythagorean triples whose small > > sides are no larger than n. > > Try it with n <= 200." > > > what is "n" ? i am guessing that it is a way to give a bound to the > > triples to be returned but i can't figure out where to fit in "n". > > > a^a + b^b = c^c is the condition to satisfy and i need to use loops > > Well, I'd interpret it to mean that > > a <= 200 > AND > b <= 200 > > since c is the hypotenuse, which by definition is longer than either of > the sides. > > The brute force approach is a nested set of "for" loops, running > 1-200 (remember that (x)range(200) runs 0-199 ). > > The alternative is to study the information at > > http://www.math.uic.edu/~fields/puzzle/triples.html > > and filtering out entries where the first two components are >200... > Looking at the middle term "2*m*n" would have to be less than 201, and > the first term "n*n-m*m" < 201 > > In Python, this can all be done in a one-liner... > > [(n*n - m*m, 2*m*n, n*n + m*m) for n in xrange(2,101) for m in > xrange(1,n) if 2*m*n < 201 and n*n-m*m < 201] > > Converting this to a clean set of nested loops and nice lines of > output is a different matter. > > Oh, and DO study the link I gave so you can cite it when you turn in > this intriguing formulation... after all, no need for math.sqrt > > -- > Wulfraed Dennis Lee Bieber AF6VN > wlfr...@ix.netcom.com HTTP://wlfraed.home.netcom.com/ Hi Wulfraed, only a has an upper limit of 200 the program needs to output the following triple for a == 200: (200 , 609,641) so at this stage my problem is: how to set the upper limit for b in a smart way? My solution below is not efficient i believe. import math for a in range (190,200): for b in range (a,a*a): csqrd = a * a + b * b csqrt = math.sqrt(csqrd) for c in range (1, csqrd): if c * c == a * a + b * b and math.floor(csqrt) == csqrt: print (a,b,c) -- http://mail.python.org/mailman/listinfo/python-list
Re: pythagorean triples exercise
On 10/21/2010 7:55 PM, Baba wrote: the bit i'm having difficulties with in constructing my loops is: "whose small sides are no larger than n" from math import sqrt def py_trips(n): for b in range(4,n+1): for a in range(3,b+1): cf = sqrt(a*a+b*b) c = int(cf) if c == cf: yield a, b, c for t in py_trips(200): print(t) # prints (3,4,5) ... (150, 200, 250) This version assumes that if a*a+b*c is an exact square of an integer, the floating point sqrt will be an exact integral value, which I believe it should be for values up to the max (for n max 200) of 8. It produces multiples of each triple, such as (3,4,5), (6,8,10), (9,12,15), ... (150,200, 250), which a different formulation of the problem might exclude, to only ask for 'basic' triples of relatively prime numbers. -- Terry Jan Reedy -- http://mail.python.org/mailman/listinfo/python-list
Re: pythagorean triples exercise
On Oct 21, 10:18 pm, Terry Reedy wrote: > On 10/21/2010 6:55 AM, Baba wrote: > > > Hi everyone > > > i need a hint regarding the following exercise question: > > > "Write a program that generates all Pythagorean triples whose small > > sides are no larger than n. > > This is not well worded. I take 'small sides' (plural) to mean the two > smaller, non-hypotenuse sides (which are necessarily shorter than the > hypotenuse). So the possible pairs of values i,j, where i is the shorter > of the two, have > > > Try it with n<= 200." > > Again, not well worded; I believe this is meant to be n==200, except > that the program should take n as a parameter and then give it value > 200, so that the could work if n were given some other value. > > So the possible pairs of values i,j, where i is the shorter of the two, > have j <= n (==200) and i <= j. > > -- > Terry Jan Reedy Hi Terry, the full exercise reads as follows: Write a program that generates all Pythagorean triples whose small sides are no larger than n. Try it with n <= 200. (Hint: Use two for loops to enumerate possible values for the small sides and then test to determine whether the result is an integral square. source: http://users.soe.ucsc.edu/~pohl/12A/ch03-state.pdf (exercise 11, it's a Java book but i like to use Python for solving such basic exercises as it is a much less cumbersome language) i agree that possibly the wording makes this more difficult than it is. Anyway, i'm a beginner so my problem solving techniques are still quite shaky. the bit i'm having difficulties with in constructing my loops is: "whose small sides are no larger than n" i don't know what to do with that :( Baba -- http://mail.python.org/mailman/listinfo/python-list
Re: pythagorean triples exercise
On 10/21/2010 6:55 AM, Baba wrote: Hi everyone i need a hint regarding the following exercise question: "Write a program that generates all Pythagorean triples whose small sides are no larger than n. This is not well worded. I take 'small sides' (plural) to mean the two smaller, non-hypotenuse sides (which are necessarily shorter than the hypotenuse). So the possible pairs of values i,j, where i is the shorter of the two, have Try it with n<= 200." Again, not well worded; I believe this is meant to be n==200, except that the program should take n as a parameter and then give it value 200, so that the could work if n were given some other value. So the possible pairs of values i,j, where i is the shorter of the two, have j <= n (==200) and i <= j. -- Terry Jan Reedy -- http://mail.python.org/mailman/listinfo/python-list
Re: pythagorean triples exercise
What you want is to realize that all integer Pythagorean triples can be generated by a pair of integers, (i,j), j < i. The values are just (* = multiply, ^ = exponentiation) a = 2*i*j b = i^2 - j^2 c = i^2 + j^2 (hypotenuse) So yes indeed a^2 + b^2 = c^2. This is a very ancient result, btw and used to be taught in public schools until recently. So the programming problem is to sort through these and toss out all triangles for which the short side (a or b, it will vary) is less than or equal to n. Or you could be Math-y and use an inequality argument to find when a or b is the short side (bit of work). Hope this helps... - Original Message - From: "Baba" To: python-list@python.org Sent: Thursday, October 21, 2010 5:51:07 AM Subject: pythagorean triples exercise Hi everyone i need a hint regarding the following exercise question: "Write a program that generates all Pythagorean triples whose small sides are no larger than n. Try it with n <= 200." what is "n" ? i am guessing that it is a way to give a bound to the triples to be returned but i can't figure out where to fit in "n". a^a + b^b = c^c is the condition to satisfy and i need to use loops and "n" will be an upper limit of one (or more?) of the loops but i am a bit lost. Please help me get thinking about this right. exercise source: Java by Dissection (Ira Pohl and Charlie McDowell) thanks Baba -- http://mail.python.org/mailman/listinfo/python-list -- http://mail.python.org/mailman/listinfo/python-list
Re: pythagorean triples exercise
On 10/21/10, Baba wrote: > Hi everyone > > i need a hint regarding the following exercise question: > > "Write a program that generates all Pythagorean triples whose small > sides are no larger than n. > Try it with n <= 200." > > what is "n" ? i am guessing that it is a way to give a bound to the > triples to be returned but i can't figure out where to fit in "n". Picture a right triangle. The two short sides (the two sides coming off either side of the right angle) must be no longer than n. The lengths of these two sides are a and b, and you are looping until either side exceeds n... HTH. > > a^a + b^b = c^c is the condition to satisfy and i need to use loops > and "n" will be an upper limit of one (or more?) of the loops but i am > a bit lost. Please help me get thinking about this right. > > import math > for b in range(20): > for a in range(1, b): > c = math.sqrt( a * a + b * b) > if c % 1 == 0: > print (a, b, int(c)) > > this returns > > (3, 4, 5) (6, 8, 10) (5, 12, 13) (9, 12, 15) (8, 15, 17) (12, 16, 20) > > is that the desired output? what is the step that i'm missing? > > thanks in advance > > Baba > p.s. this is not homework but self-study > -- > http://mail.python.org/mailman/listinfo/python-list > -- Have a great day, Alex (msg sent from GMail website) mehg...@gmail.com; http://www.facebook.com/mehgcap -- http://mail.python.org/mailman/listinfo/python-list