Real Ultimate Programming

The Home for People Who Like to Flip Out and Write Code

Project Euler: Problem 9

Problem 9 deals with one of the more interesting things I learned in high school geometry: Pythagorean triples. In high school, I just memorized the 2 most common ones (3, 4, 5 and 5, 12, 13) and thought to myself: Wouldn’t it be cool if I could generate all of these? But that was in the before time; Wikipedia didn’t exist and my text book wasn’t cool enough to dwell on them. At any rate, now I know Euclid’s formula for generating Pythagorean triples:

m ** 2 - n ** 2, 2 * m * n, m ** 2 + n ** 2

Here’s the script I used to solve the actual problem:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

    """Solves Problem 9 from Project Euler."""
    import operator

    def triples(upper_bound):
        """Generator for Pythagorean Triples (represented as tuples).

        Uses Euclid's formula to generate Pythagorean Triples
        (see http://en.wikipedia.org/wiki/Pythagorean_triple#Generating_a_triple).
        """
        for m in xrange(2, upper_bound):
            for n in xrange(1, m):
                yield m ** 2 - n ** 2, 2 * m * n, m ** 2 + n ** 2
    # Only uncomment if the triples we get from the original Euclid's are insufficient.
    # for k in xrange(1, upper_bound):
    #     yield k * (m ** 2 - n ** 2), k * (2 * m * n), k * (m ** 2 + n ** 2)

    def problem_9():
        """Finds the product of the Pythagorean Triple where a + b + c = 1000."""
        for triple in triples(1000):
            if sum(triple) == 1000:
                return reduce(operator.mul, triple)
        return 0

    if __name__ == '__main__':
        print problem_9()

Back to flipping out…