0x000a - Project Euler 009

Problem:

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which, a2 + b2 = c2

For example, 32 + 42 = 9 + 16 = 25 = 52.

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

Solution:

1. Brute-force approach:

s = 1000
for a in range(3, s) :
    for b in range(a+1, s) :
        c = s-a-b
        if c**2 == a**2 + b**2:
            print a*b*c
            exit

2. Efficient approach:

from math import sqrt
s = 1000
limit = int(sqrt(s))

for n in range(1, limit, 2) :
    for m in range(n+1, limit, 2) :
        a, b, c = m**2 - n**2, 2*m*n, m**2 + n**2
        if a+b+c == s:
            print a*b*c
            exit

Analysis:

The simplest method to solve this problem would be the brute-force approach. According to this, we assign values to a and b, then calculate c as 1000 – a – b. If a, b and c satisfy Pythagorean Theorem, their product abc is printed to the standard output and the program exits.

Now, we are told that a, b and c are natural numbers such that a < b < c. Also, the smallest element in a Pythagorean Triple is 3. Thus, the outer loop for a has a lower limit of 3 and the upper limit as s – 1. As b > a, the inner loop for b starts from *a+*1. Clearly, as a+b+c = 1000, c will have the value 1000 – a – b. If the triple (a, b, c) satisfy Pythagorean Theorem, their product is the answer. To prevent the program from printing combinations of the triple, we exit after printing the result.

In the efficient approach, I’ve used Euclid’s Formula, which is a fundamental formula for generating Pythagorean triples. The formula states that the integers

form a Pythagorean triple, where m > n. In the program, as m > n, the lower limit of m is *n+*1. The upper limit of both m and n is the square root of the perimeter s, floored to the nearest integer. The values of a, b and c are calculated using the above formula, and if they add up to 1000, their product is returned as the result.

Running time:

Using Python 2.7 under the Ubuntu 10.10 terminal, the following times were clocked for the two approaches:

1. Brute-force approach: 229.737 milliseconds

2. Efficient approach: 0.167 milliseconds, which is about 0.0746% of the time taken by brute-force, making it more than 1339 times faster.