CODEWITHSUNDEEP
algorithm
user425727
user425727

Reputation:

finding pythagorean triples (a,b,c) with a <=200

In my previous post on this subject i have made little progress (not blaming anyone except myself!) so i'll try to approach my problem statement differently.

how do i go about writing the algorithm to generate a list of primitive triples?

all i have to start with is:

a) the basic theorem: a^2 + b^2 = c^2

b) the fact that the small sides of the triple (a and b) need to be smaller than 'n'

(note: 'n' <= 200 for this purpose)

How do i go about building my loops? Do i need 2 or 3 loops?

a professor gave me some hints but alas i am still lost. I don't know where to start with building my loops. Do i need 2 or 3 loops? do i loop through a and b or do i need to introduce the 'n' variable into a loop of its own? This probably looks like obvious hints to experienced programmers but it seems i need more hand holding still...any help will be appreciated!

A Pythagorean triple is group of a,b,c where a^2 + b^2 = c^2. you need to find all a,b,c combinations which satisfy the above rule starting a 0,0,0 up to 200 ,609,641 The first triple will be [3,4,5] the next will be [5,12,13] etc.. n is length of the small side a so if n is 5 you need to check all triples with a=1,a=2,a=3,a=4,a=5 and find the two cases shown above as being Pythagorean,

EDIT

thanks for all submissions. So this is what i came up with (using python)

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))

this DOES return the triple (200 ,609,641) where 200 is the upper limit for 'a' but computing the upper limit for 'b' remains tricky. Not sure how i would go about this...suggestions welcome :)

Thanks

Baba

p.s. i'm not looking for a solution but rather help in improving my problem solving skills. (definitely needed :-) )

Upvotes: 2

Views: 3597

Answers (6)

FatherStorm
FatherStorm

Reputation: 7183

leaving the formula and the language alone, you're trying to find every combination of two variables, a and b so...

foreach A   
  foreach B  
    foreach C
      do something  with B and A  and eval with c  
    end foreach C  
  end foreach B  
end foreach A

for ($x = 1; $x <= 200; $x++) {
    for ($y = 1; $y <= 200; $y++) {
        for ($z = 1; $z <= 200; $z++) {
            if ($x < $y) {
                if (pow($x, 2) + pow($y, 2) == pow($z, 2)) {
                    echo "$x, $y , $z<br/>";
                }
            }
        }
    }
}

3, 4 , 5
5, 12 , 13
6, 8 , 10
...

81, 108 , 135
84, 112 , 140
84, 135 , 159

Upvotes: 0

David Thornley
David Thornley

Reputation: 57036

To compute the upper limit of b ... certainly we can't go past a^2 + b^2 = (b+1)^2, since the gap between successive squares increases. Now, (b+1)^2 is b^2 + 2b + 1, so we can stop on b when a^2 < 2b + 1. (In fact, for odd a, the biggest triple is when b = (a^2 - 1)/2, and then a^2 + b^2 = (b+1)^2.)

Let's consider even a. Then, we need to consider a^2 + b^2 = (b+2)^2, since 2b+1 is necessarily odd. Now, (b+2)^2 - b^2 = 4b+4, so we're looking at a^2 = 4b+4, or b = (a^2 - 4)/4 as the highest b (and, as before, we know this b works).

Therefore, for given a, you need to check bs up to

(a^2 - 1)/2 (a odd)

(a ^2 - 4)/4 (a even)

Upvotes: 1

Jacob
Jacob

Reputation: 34601

Break the problem into sub problems. The first clue is that you have an upper bound n on the value of c. Let's start with c=1 --- so, let's see how many triplets can be formed with:

a^2 + b^2 = 1

Now, let's set a = 1 to c-1. So that means we have to check if b is an integer such that b^2 = c^2 - a^2 and b^2 = int(b)^2.

Upvotes: 0

jlv
jlv

Reputation: 617

So Pythagorean tripes luckily have two properties that make this not so bad to solve:

First, all the numbers in a triple have to be integers (that means, you can calculate a^2 + b^2 and you have a triple if c^2 is an integer and not a float). Additionally, c is bounded by what a and b are.

So this should inform you how many variables you really have (which will guide your algorithm design - specifically how many for loops you need). The latter piece of information will inform you as to how long of a range you need to iterate over. I've tried to be vague as per your request, but let me know if you'd like anything more specific.

Upvotes: 0

JoshD
JoshD

Reputation: 12824

Given any a and b, you can compute what c should be. You can also check if the c you get is a whole number. With that in mind, you need to check all the a and b values and find the ones that give you a whole c number.

This should take just two loops (one for a and one for b). Leave comments if you want more help, and let me know what problems you have.

Upvotes: 0

IVlad
IVlad

Reputation: 43477

You only need two loops. Note that n is given, meaning you read it from the keyboard or from a file.

Once you read n, you simply loop a from 1, then in that loop you loop b from a. Then you check if a <= n and if b <= n. If yes, you check if a^2 + b^2 is a square (if it can be writen as c^2 where c is an integer). If yes you output the corresponding triplet. You can stop the first loop once a > n and the second loop once b > n.

Upvotes: 1

Related Questions