I’m trying to find ‘highly composite’ pythagorean triples - numbers (c) that have more than one unique a,b (in the naturals) that satisfy a^2 b^2 = c^2.

I’ve written a short python script to find these - it cycles through c in the range (0,1000), and for each c, finds all possible (a,b) such that b < a < c. This is a more brute force method, and I know if I did some reading on number theory I could find some more methods for different cases of a and b.

I have a feeling that my script isn’t particularly efficient, especially for large c. I don’t really know what to change or how to make it more efficient.

I’d be really grateful for any help or pointers!

a = 0 
b = 0
l=[]
for i in range (0,1000):
#i is our c.
    while a<i:
        while b<a:

        #for each a, we cycle through b = 1, b = 2, … until b = a. 
        #Then we make b = 0 and a = a 1, and start the iterative process again.

            if a*a   b*b == i*i:
                l.append(a)
                l.append(b)

                #I tried adding a break here - my thought process was that we can’t find any 
                #other b^2 that satisfies a^2   b^2 = i^2 without changing our a^2. This 
                #actually made the runtime longer, and I don’t know why.

            b = b 1

        a = a 1
        b = 0

    if len(l) > 4:

        #all our pairs of pythagorean triples, with the c at the end.
        print(l, i)
    
    #reset, and find pairs again for i = i 1.
    l = []
    b = 0
    a = 0

CodePudding user response：

Your code seems quite inefficient, because you are doing many times the same computations. You could make it more efficient by not calculating things that are not useful. The most important detail is the computation of a and b. You are looping through all possible values for a and b and checking if it's a pythagorean triplet. But once you give yourself a value for a, there is only one possible choice for b, so the b loop is useless.

By removing that loop, you're basically lowering the degree of the polynomial complexity by one, which will make it increasingly faster (compared to your current script) when c grows

Also, your code seems to be wrong, as it misses some triplets. I ran it and the first triplets found were with 65 and 85, but 25, 50 and 75 are also highly composite pythagoren triplets. That's because you're checking len(l)>4, while you should check len(l)>=4 instead because you're missing numbers that have two decompositions.

As a comparison, I programmed a similar python script as yours (except I did it myself and tried to make it as efficient as possible). Your script ran in 66 seconds, while mine ran in 4 seconds, so you have a lot of room for improvement.

CodePudding user response：

#There is a general formula for pythagoran triples
take 2 numbers, m & n where m > n
    a = (m^2) - (n^2)
    b = 2mn
    c = (m^2)   (n^2)
That will always give you a pythagoran triple. Its more efficient but it might not be what you're looking for.