Project Euler 125

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


2乗和の公式を使えば、

m2 + … + n2 = n(n+1)(2n+1) / 6 - (m-1)m(2m-1) / 6

あとは回文数の判定をするだけです。

from itertools import *

def gen_digits(n):
    while n:
        yield n % 10
        n /= 10

def reverse(n):
    return reduce(lambda x, y: x * 10 + y, gen_digits(n))

def is_palindromic(n):
    return reverse(n) == n

def gen_sum_square_sequences(n):
    limit = int((n / 2) ** 0.5)
    for s in xrange(1, limit):
        m = (s - 1) * s * (2 * s - 1) / 6
        for t in takewhile(lambda t: t < n,
                    (e * (e + 1) * (2 * e + 1) / 6 - m
                    for e in count(s + 1))):
            yield t

N = 10 ** 8
print sum(ifilter(is_palindromic, gen_sum_square_sequences(N)))