How to Efficiently Generate Pythagorean Triples in Python?

[trollcast]

Homework Statement

Generate a list of the first n pythagorean triples.

Homework Equations

a^2=b^2+c^2

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:

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

 

[mfb]

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

 

[trollcast]

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

I would expect that this code does not need significant time for n<100. Do you need more?

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.

 

[mfb]

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.

 

[trollcast]

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.

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.

 

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