2
\$\begingroup\$

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
                break

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

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

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.

\$\endgroup\$
  • 4
    \$\begingroup\$ Isn't the sum actually 2*k*u*(u+v)? \$\endgroup\$ – Jaime Jul 30 '14 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 '14 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 '14 at 6:58
  • \$\begingroup\$ @Stuart The proposed algorithm is O(d(n)^2), isn't it obvious? \$\endgroup\$ – vnp Jul 31 '14 at 7:16
  • 1
    \$\begingroup\$ The algorithm is O(1) and reduces to: print 31875000 \$\endgroup\$ – Emanuele Paolini Aug 6 '14 at 21:22
4
\$\begingroup\$

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):
            c=1000-(a+b)
            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

\$\endgroup\$
  • \$\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 '14 at 13:02
4
\$\begingroup\$
  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.

\$\endgroup\$

protected by Malachi Aug 6 '14 at 19:47

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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