# Homework Help: Generating Pythagorean Triples

1. Feb 24, 2013

### trollcast

1. The problem statement, all variables and given/known data
Generate a list of the first n pythagorean triples.

2. Relevant equations
a^2=b^2+c^2

3. The attempt at a solution

This is what I've came up with in python but I'm sure its not the most efficient way I could have done it:

Code (Text):
import math

n = int(raw_input("Input a number: "))

trips_found = 0
c = 4

while trips_found < n:
c += 1
csquared = c * c
a = 3
while a < c:
asquared = a * a
bsquared = csquared - asquared
b = math.sqrt(bsquared)

if b % 1 ==0:
print "(" + str(a) + ", " + str(int(b)) + ", " + str(c) + ")"
trips_found += 1

a += 1

2. Feb 24, 2013

### Staff: Mentor

"First", ordered by what?
There are formulas to generate those triples, but I don't know if they find all options.

Runs in <1s for n=1000 and ~15s for n=10000 here, not counting output. Do you need more?

Edit: You find all triples twice (with a and b switched).

Last edited: Feb 24, 2013
3. Feb 24, 2013

### trollcast

First ordered by the largest value of the triple ie.

(3, 4, 5)
(4, 3, 5)
(6, 8, 10)
(8, 6, 10)
(5, 12, 13)
(12, 5, 13)
(9, 12, 15)
(12, 9, 15)
.
.
.

Its not too bad for time but I was just wondering if there was a more direct way of finding them since that was quite like a brute force solution.

4. Feb 24, 2013

### Staff: Mentor

For 100 000 it takes some time now.

A first easy step would be to stop testing at c/sqrt(2). This removes all doubled entries, too (you can add them manually again if you like), but the speedup is just about this factor of 1/sqrt(2).

There are formulas which find all triples.

Edit: Oh, done! 844 seconds for n=100 000.

Last edited: Feb 24, 2013
5. Feb 24, 2013

### trollcast

I timed it for n = 10000 and it took about 30 seconds on my pc.

I'll have a look for one of those formulae to see if it would work better.

6. Feb 24, 2013

### trollcast

I could maybe use the fact that some triples are just multiples of other triples, eg. (6,8,10) is just 2x (3,4,5).