Pythagorean triplets

Exercism
1

getting nothing but timeout errors even though it manages to run locally. but i’m guessing iteration is probably just not the way to go.

def triplets_with_sum(number):
    a = 1
    triplist = []
    while True:
        for b in range(a+1, number):
            c = number - a - b
            if a ** 2 + b ** 2 == c ** 2:
                break
            else:
                if b > number//2:
                    break
        if b > number//2:
            if c < 0:
                break
            a += 1
            continue
        else:
            if a >= b:
                break
            elif a + b + c == number:
                triplist.append([a, b, c])
                a += 1
                continue
            else:
                a += 1
                continue
    return triplist
2

It is really hard to read that code since it is not properly formatted. Since this is python, spacing matters. Please use the control that looks like </>, and paste your code into where type of paste code here is displayed. However, if I had to guess, I’d say that you have an infinite loop, but I won’t know that until I see the code properly formatted.

3

This exercise does require some optimization to run in a reasonable time and not time out.

4

fixed the formatting

5

@keegopeo I ran you code locally, and it does work. However, the test case where number is 30000 takes a very long time. As @IsaacG said, the key to getting this to run in a reasonable amount of time is to optimize your solution. In other words, try to minimize the number of combinations of a and b that your code is searching over. When I solved this problem, I started with this expression:

a**2 + b**2 == (number - a - b)**2

Using that equation, given a value of a you can find a corresponding value of b. However, b is only valid if it is an integer that is greater than a. You’ll need to work through the algebra to discover that relationship.

1 Like
6

yeah, i think i might need to fix up my code. guess it’s time to read up on some math.

7

The best idea, in my opinion, is to use the formulas proven by Euclid:

a = m^2 - n^2
b = 2mn
c = m^2 + n^2

where m and n are relatively prime integers with opposite parity (one is odd, one is even). This lets you generate all primitive triples up to the limit quickly, and then you just need to pick the ones where the sum is a divisor of the desired total.

1 Like