Project Euler problem 9

Source code available on GitHub.

This problem is as follows:

I initially looked at this problem and tried to overcomplicate it quite a lot. I know of ways of generating Pythagorean triplets and tried to implement something much more fancy than necessary. I kept not getting the answer, possibly because in its base form the Euclid method does not generate all triplets.

Anyway, I got rid of that solution and went back to the start; a really quite simple program is more than sufficient for this program.

I like breaking things up into functions, partly because it looks nice but also because it means I can much more easily use bits from my previous programs in later ones. So, I started by making a function called `PythagoreanTriple(N)` which will generate a Pythagorean triplet that sums to `N`. So, we want three numbers, let’s call them `x`, `y` and `z`, such that `x + y + z == N` and `z*z == x*x + y*y`. Let’s assume `x < y` (it could be the other way round but then we’d just switch `x` and `y`). Now, it’s clear that `x < y < N` and so we can get started with a simple `for` loop:

def PythagoreanTriple(N): # Generates a pythagorean triple that sums to N
    for x in range(1,N+1):
        for y in range(x+1,N+1):

Now by the time we’re inside this second for loop, we know the current values of x and y so it seems a bit pointless to start again generating all possible values of z and checking whether z*z == x*x + y*y. We can do better: obviously while the square of z is less than x*x + y*y (which we already know), we can just keep increasing z. Only once we know z*z >= x*x + y*y do we actually need to check the equality:

def PythagoreanTriple(N): # Generates a pythagorean triple that sums to N
    for x in range(1,N+1):
        for y in range(x+1,N+1):
            z = y + 1
            while z*z < x*x + y*y:
                z += 1
            if z*z == x*x + y*y and x+y+z == N:
                return [x,y,z]
    return 'Failed'

Of course once we get out our special triplet we need the product x*y*z (or in the question). We could easily do it by hand but let’s port in our prod() function from the last question and use that:

def prod(iterable):
    product = 1
    for i in iterable:
        product *= i
    return product

def PythagoreanTriple(N): # Generates a pythagorean triple that sums to N
    for x in range(1,N+1):
        for y in range(x+1,N+1):
            z = y + 1
            while z*z < x*x + y*y:
                z += 1
            if z*z == x*x + y*y and x+y+z == N:
                return [x,y,z]
    return 'Failed'

print(prod(PythagoreanTriple(1000)))