Project Euler 80

Problem 80
自然数平方根が整数でなければ、無理数であることが知られている。このような平方根の小数の展開は無限で繰り返しはない。
2の平方根は1.41421356237309504880...で、最初の100桁の各桁の和は475である。
最初の100個の自然数に対して、無理数平方根の最初の100桁の各桁の和のすべての和を求めよ。
http://projecteuler.net/index.php?section=problems&id=80

昔習った平方根を求める方法をシミュレートしてみました。すなわち、


1.41
1 /2
1 1
24 100
4 96
281 400
1 281
282 11900

from itertools import dropwhile, count

def head(a):
    for e in a:
        return e

def take(n, a):
    counter = 0
    for e in a:
        yield e
        counter += 1
        if counter == n:
            break

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

def square_root(n, l, m = 0):
    if l == 0:
        return m
    
    d = head(dropwhile(lambda d: d * (d + 20 * m) <= n, count(1))) - 1
    n -= d * (d + 20 * m)
    m = m * 10 + d
    return square_root(n * 100, l - 1, m)

N = 100
M = 100
print sum(map(lambda n: sum(gen_digits(square_root(n, M))),
        filter(lambda n: square_root(n, 1) ** 2 != n, range(1, N + 1))))