CODEWITHSUNDEEP
pythonpythagorean
Sam Corrigan
Sam Corrigan

Reputation: 23

Python Primitive Pythagorean triple code not working

Currently trying to find all primitve pytagorean triples up to some number n, using the formula a = m^2-n^2, b = 2mn, c = m^2 + n^2. Here is the code:

    def prim(k):
        primlist=[]
        for m in range(1,k):
            for n in range(m+1,k+1):
                if m**2+n**2>k:
                    break
                if m%2==1 and n%2==1:
                    break
               if n**2-m**2==0 or 2*m*n ==0 or n**2+m**2==0:
                    break

                if gcd(m,n)!=1:
                    break


                primlist.append([n**2-m**2,2*m*n,n**2+m**2])
        return primlist
    print(prim(100))

We expect to find all pythagorean triples, however some are missing, for example 20,21,29. Theres 16 with c under 100 however we only get 6. Cheers

Upvotes: 2

Views: 1381

Answers (1)

PM 2Ring
PM 2Ring

Reputation: 55469

Apart from the first condition, where m & n are too large, you don't want to break out of the inner loop, simply continue on to the next iteration.

The following tests are completely superfluous, since with your m and n they can never be true.

if n**2-m**2==0 or 2*m*n ==0 or n**2+m**2==0:

so I've removed them from the code. You didn't supply a gcd function, or import one from the standard library, so I've supplied my own.

def gcd(a, b):
    '''  Greatest common divisor of a & b '''
    while b:
        a, b = b, a % b
    return a

def prim(k):
    primlist=[]
    for m in range(1,k):
        for n in range(m+1,k+1):
            if m**2 + n**2 > k:
                break
            if m%2==1 and n%2==1:
                continue
            if gcd(m,n)!=1:
                continue

            primlist.append([n**2 - m**2, 2*m*n, n**2 + m**2])
    return primlist

print(prim(100))

output

[[3, 4, 5], [15, 8, 17], [35, 12, 37], [63, 16, 65], [5, 12, 13], [21, 20, 29], [45, 28, 53], [77, 36, 85], [7, 24, 25], [55, 48, 73], [9, 40, 41], [33, 56, 65], [65, 72, 97], [11, 60, 61], [39, 80, 89], [13, 84, 85]]

FWIW, here's a more efficient (and slightly more Pythonic) way to write that code. Rather than building a list, we make a generator. That way we can just print or consume the triples, and of course we can easily collect them into a list by doing, eg list(prim(100)).

def gcd(a, b):
    '''  Greatest common divisor of a & b '''
    while b:
        a, b = b, a % b
    return a

def prim(k):
    for m in range(1, k):
        for n in range(m+1, k+1):
            m2, n2 = m * m, n * n
            if m2 + n2 > k:
                break
            if m % 2 and n % 2:
                continue
            if gcd(m, n) > 1:
                continue

            yield n2 - m2, 2*m*n, n2 + m2

for i, t in enumerate(prim(100), 1):
    print(i, t)

output

1 (3, 4, 5)
2 (15, 8, 17)
3 (35, 12, 37)
4 (63, 16, 65)
5 (5, 12, 13)
6 (21, 20, 29)
7 (45, 28, 53)
8 (77, 36, 85)
9 (7, 24, 25)
10 (55, 48, 73)
11 (9, 40, 41)
12 (33, 56, 65)
13 (65, 72, 97)
14 (11, 60, 61)
15 (39, 80, 89)
16 (13, 84, 85)

Upvotes: 2

Related Questions