I am doing this Project Euler Question #9:

A Pythagorean triplet is a set of three natural numbers, \$a < b < c\$, for which,

$$a^2 + b^2 = c^2$$

For example, \$3^2 + 4^2 = 9 + 16 = 25 = 5^2\$.

There exists exactly one Pythagorean triplet for which \$a + b + c = > 1000\$.
Find the product \$abc\$.

I have implemented the code but I feel like it runs slow and doesn't perform well enough:

def check_pathagorean(a, b, c):
    return (a**2) + (b**2) == (c**2)

SUM = 1000

for i in range(1, SUM):
    for j in range(i+1, SUM):
        c = SUM - (i + j)
        if(check_pathagorean(i, j, c)):
            if i + j + c == SUM:
                print i * j * c

What could I do to make this run faster and better?

  • 1
    \$\begingroup\$ You might want to look up Berggren's algorithm to generate the Pythagorean triples. \$\endgroup\$ Jul 30, 2014 at 19:12
  • \$\begingroup\$ You mean =1000 not >=1000 \$\endgroup\$ Aug 6, 2014 at 21:14

3 Answers 3


Any pythagorean triple is in form of

$$ k(u^2 - v^2), 2kuv, k(u^2 + v^2) $$

where u, v, and k are positive integers with u > v, u − v odd, and with u and v coprime. The sum is therefore

$$ ku(u + 2v) $$

(the restrictions still apply).

Now your job is factor 1000 into 3 terms (not so many ways to do so, 1000 = 5*5*5*2*2*2) and determine if those terms can be represented with u and v being coprime with an odd difference.

  • 5
    \$\begingroup\$ Isn't the sum actually 2*k*u*(u+v)? \$\endgroup\$
    – Jaime
    Jul 30, 2014 at 20:11
  • 1
    \$\begingroup\$ And k does not have to be a positive integer... The solution to this one has u = 25; v = 15; k = 1/2. \$\endgroup\$
    – Jaime
    Jul 30, 2014 at 20:27
  • \$\begingroup\$ It would be useful to add something about whether/how this proposed algorithm would actually improve on the original idea, in terms of speed/complexity. \$\endgroup\$
    – Stuart
    Jul 31, 2014 at 6:58
  • \$\begingroup\$ @Stuart The proposed algorithm is O(d(n)^2), isn't it obvious? \$\endgroup\$
    – vnp
    Jul 31, 2014 at 7:16
  • 1
    \$\begingroup\$ The algorithm is O(1) and reduces to: print 31875000 \$\endgroup\$ Aug 6, 2014 at 21:22

Because of the ratio of a,b,c in a Pythagorean triplet no variable can ever be larger than half the sum of a+b+c therefore I have lowered the upper limit to 500 or SUM/2. Then, as Stuart mentioned, the if i + j + c == SUM is redundant. Finally by using xrange and eliminating the call to another function we have this.

def pythagorean():
    for a in xrange(500):
        for b in xrange(a+1,500):
            if a**2+b**2==c**2:
                return a*b*c

These changes brought the run time down from 0.119642019272 to 0.0286219120026 seconds

  • \$\begingroup\$ +1 nice observation. The Both loops are reduces by the factor \$\frac{1}{2}\$ so the whole algorithm is reduced by the factor \$\frac{1}{4}\$ \$\endgroup\$
    – miracle173
    Aug 24, 2014 at 13:02
  1. if i + j + c == SUM is not needed as you have already set c = SUM - (i + j)

  2. When you find the result and break out of the inner loop, you are not breaking out of the outer loop, so the programme will continue through all possible values of i and j. Fix this by putting the loop inside a function and returning the value.

  3. Think about the fact that c must be larger than i and j, which reduces the ranges that you have to loop over.

  4. However some further algebra reveals that there is no need to loop over j at all. This is because you can make j the subject of

$$i^2 + j^2 = (SUM - i - j)^2 $$

and calculate a unique solution given i and SUM. You then just have to check if it is an integer.

This step also allows us to calculate the exact range over which we can loop i. Given that i < j, the maximum value of i turns out to be 1 - sqrt(1/2) times the SUM.


Not the answer you're looking for? Browse other questions tagged or ask your own question.