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))))