Project Euler Problem 80 Solution

Question

It is well known that if the square root of a natural number is not an integer, then it is irrational. The decimal expansion of such square roots is infinite without any repeating pattern at all.

The square root of two is 1.41421356237309504880…, and the digital sum of the first one hundred decimal digits is 475.

For the first one hundred natural numbers, find the total of the digital sums of the first one hundred decimal digits for all the irrational square roots.

Haskell

isqrt :: Integer -> Integer
isqrt 0 = 0
isqrt 1 = 1
isqrt n = head $ dropWhile (\x -> x*x > n) $ iterate (\x -> (x + n `div` x) `div` 2) (n `div` 2)

digits :: Integer -> [Integer]
digits = map (read . return) . show

sqrtDigits :: Integer -> Integer -> [Integer]
sqrtDigits count x = digits $ isqrt $ x*(10^(2*count))

isSquare :: Integer -> Bool
isSquare n = root * root == n
    where root = round $ sqrt $ fromIntegral n

main :: IO ()
main = print $ sum $ concat [ds | n <- [1..99], not $ isSquare n, let ds = sqrtDigits 99 n]
$ ghc -O2 -o root-expansion root-expansion.hs
$ time ./root-expansion
real   0m0.049s
user   0m0.044s
sys    0m0.004s

Questions? Comments? Send me an email: z@chdenton.com