pythagorean triples exercise

i need a quick 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 "no longer than n" all about ??

exercise source: Java by Dissection (Ira Pohl and Charlie McDowell)

note: i found what looks to be a very good post on pythagorean triples but i won't read it yet as it might spoil my attempt to solve this myself....

EDIT

if n is length of the small side a and we say: n is 5; then i need to check all triples with a=1,a=2,a=3,a=4,a=5 and find the cases that are Pythagorean triples

what is this extra condition good for?

EDIT 2

maybe i'll get closer if i show you a practical piece...so here is a short piece of (python) code that returns a few triples. I've set the upper limit for the outer loop to 20 (for now i can't see any other use for 'n') to keep it managable for the post.

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

Pythagorean triples are the integer sides of a right triangle. The small sides of the triangle are the sides that form the right angle (meaning not the hypotenuse).

no larger than n means you are given an integer n and must generate all possible triples of integers a b c such that a <= n, b <= n and a^2 + b^2 = c^2.

The question simply means that if we assume 'a', 'b' and 'c' as sides of triangle and 'c' is hypotenuse, then 'a' and 'b' both should be less than 'n'.

i.e. a <= n and b <= n

There are an infinite number of Pythagorean triples. Therefore, if you do not place bounds on the set of triples to generate, a program cannot complete the task in finite time. So we have to bound the desired output somehow. There seems to be disagreement on whether the supplied bound applies to the shortest leg or to both legs. Here, we show that bounding the shortest leg implies a bound on the other leg.

We may take a <= b < c. Since we know sqrt(2) is irrational, we can eliminate the possibility that a = b, leaving a < b < c. Since in a Pythagorean triple we have a^2 + b^2 = c^2 and a is not zero, c >= b+1 (i.e. c is at least as big as the smallest thing that c could be). Taking c to be as small as this bound, we get a^2 + b^2 = c^2 >= (b+1)^2 and this implies a^2 >= 2b+1 or b <= (a^2 - 1)/2.

So, a bound on a is also a bound on b (and therefore c). In detail, if we require a <= n, then we have required b <= (n^2 - 1)/2. We can deduce further that c^2 <= n^2 + (n^2 - 1)^2/4.

The bound on c is pretty loose, so I wouldn't recommend looping on c then filtering out too large triangles.

There will be only a finite number of PTs that exist where the longest side is less than 200 "units", therefore you can iterate through each side of the three sides, the list of integers from 1 to 200 (with some basic tests to speed the process - that's the exercise) - if they are a PT - then you've found one ( remember to ignore dupes).

Pythagorean triples can be generated automatically using a fairly simple formula. Here are some web pages that discuss:

• Pythagorean Triples
• Wikipedia: generating pythagorean triples via Euclid's formula

Also, your question about clarifying "whose small sides are no larger than n". Suppose the triple is (A,B,C) where A < B < C. (C is the hypoteneuse, A is the shorter side, B is the longer side)

Then I would interpret the requirement as finding all triples such that A <= n. (B and C could be greater than n). The question should have been more explicit and said "shortest side" ("shortest" is better than "smallest") or explicitly called out A and/or B.