1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Generating Pythagorean Triples

  1. Feb 24, 2013 #1

    trollcast

    User Avatar
    Gold Member

    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. jcsd
  3. Feb 24, 2013 #2

    mfb

    User Avatar
    2016 Award

    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
  4. Feb 24, 2013 #3

    trollcast

    User Avatar
    Gold Member

    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.
     
  5. Feb 24, 2013 #4

    mfb

    User Avatar
    2016 Award

    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
  6. Feb 24, 2013 #5

    trollcast

    User Avatar
    Gold Member

    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.
     
  7. Feb 24, 2013 #6

    trollcast

    User Avatar
    Gold Member

    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).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Generating Pythagorean Triples
  1. Speed of a generator? (Replies: 1)

  2. Generator Project (Replies: 2)

Loading...