Project Euler 142

http://projecteuler.net/index.php?section=problems&id=142

(x - y) + (y - z) = x - z

で、3つとも平方数なのでピタゴラス数であることがわかります。あとはzを決めればx, yが決まりますが、単にzの必要な範囲について調べると、20分くらいかかりました。これを、x + zが平方数という条件を入れて調べると16秒になりました。
この問題も解を小さい順に並べるのが難しいので、少し汎用のジェネレータを作りました。

def gen_sorted_list(g, init, r):
    begin = 1
    end = init - 1
    while True:
        for xyz in sorted(list(g(begin, end))):
            yield xyz
        begin = end + 1
        end = int(begin * r) - 1

from itertools import *
from math import sqrt
from fractions import gcd

def gen_square(max_n):
    return takewhile(lambda n: n <= max_n, (l * l for l in count(1)))

def gen_Pythagorean(max_n):
    for m in takewhile(lambda m: (m + 1) ** 2 + 3 <= max_n, count(2)):
        n0 = 1 if m % 2 == 0 else 2
        for n in ifilter(lambda n: gcd(m, n) == 1, xrange(n0, m, 2)):
            a = m * m - n * n
            b = 2 * m * n
            c = m * m + n * n
            A = a * a
            B = b * b
            C = c * c
            
            # y - z = a^2
            xyz_min1 = A + C + 3
            for l in gen_square((max_n - 3) / (xyz_min1 - 3)):
                yield l * A, l * C
            
            # y - z = b^2
            xyz_min2 = B + C
            for l in gen_square((max_n - 3) / (xyz_min2 - 3)):
                yield l * B, l * C

def gen_z(C, min_z, max_z):
    min_k = int(sqrt(C + min_z * 2))
    if min_k * min_k != C + min_z * 2:
        min_k += 1
    max_k = int(sqrt(C + max_z * 2))
    
    g = (k * k - C for k in xrange(min_k, max_k + 1))
    return (m / 2 for m in g if m % 2 == 0)

def gen_xyz(min_n, max_n):
    return (A + C + z * 3 for A, C in gen_Pythagorean(max_n)
        for z in gen_z(C, max(1, (min_n - A - C + 2) / 3),
                                        (max_n - A - C) / 3 + 1)
            if is_valid(C + z, A + z, z))

def is_square(n):
    m = int(sqrt(n))
    return m * m == n

def is_valid(x, y, z):
    return is_square(x + y) and is_square(x + z) and is_square(y + z)

def gen_sorted_list(g, init, r):
    begin = 1
    end = init - 1
    while True:
        for xyz in sorted(list(g(begin, end))):
            yield xyz
        begin = end + 1
        end = int(begin * r) - 1

print next(gen_sorted_list(gen_xyz, 100, 2))