８０問目

http://projecteuler.net/index.php?section=problems&id=80
2 の平方根 1.41421356237309504880... の最初の 100 桁の数字の和は 475 である。1 〜 100 の平方数で無い自然数について、最初の 100 桁の数字の総和を求める。
中学だか高校だかで習った開平法を使いました。
開平法を初めて習ったときは、なぜそれで求まるのか理解できず、好きになれなかったのですが、今回も結局分かりませんでした。

import Data.List

main = print $ euler080 100 100

euler080 :: Int -> Integer -> Integer
euler080 n m = sum [ sum $ take n $ root j |
    j <- takeWhile (<= m) $ concat [ [i^2+1..(i+1)^2-1] | i <- [1..] ] ]

root :: Integer -> [Integer]
root n = map (\ (a, b, c) -> c) $ iterate ext (n, 0, r)
    where r = floor $ sqrt $ fromIntegral n

ext :: (Integer, Integer, Integer) -> (Integer, Integer, Integer)
ext (a, b, c) = (a', b', c')
    where a' = (a - (b + c) * c) * 100
          b' = (b + c * 2) * 10
          c' = last $ takeWhile (\ n -> (b' + n) * n <= a') [0..9]