Project Euler: Problem 9

http://projecteuler.net/index.php?section=problems&id=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.

To generate the triplets, we'll use Euclid's formula (http://en.wikipedia.org/wiki/Pythagorean_triple#Generating_a_triple).

def f1(x):
    m,n = 1,0

    while True:
        m += 1

        # No solution?
        if (2*m*m + 2*m) > x:
            return None

        for n in xrange(1,m):
            # Euclid's formula
            a = m*m - n*n
            b = 2*m*n
            c = m*m + n*n

            if (a+b+c) == x:
                return a*b*c

Obviously there are many possible input values for which there are no solutions. In these cases, since 1 is the lowest possible value for n, we can check to see if m has become too large. That's the point of the "return None" statement above.