Project Euler 63,64

Problem 63

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

9までで考えればよい。

num_digits n = length (takeWhile (>0) a) where a = n:[ div n 10 | n <- a ]
count d = length (takeWhile (\(e,n) -> n == e)
                            [ (e, num_digits (d^e)) | e <- [1..] ])
main = print (sum (map count [1..9]))

Problem 64

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

最初に戻ってくるのを待てばよい。

index (x:xs) b = if x == b then 0 else p + 1 where p = index xs b
search_loop (x:y:xs) = (index xs y) + 1

period n = search_loop a where
        a = (1,0,1):[ next n x | x <- a]
        next n (a,b,c) = (div a2 d, div b2 d, div c2 d) where
            b1 = b - m * c
            c2 = a * a * n - b1 * b1
            a2 = a * c
            b2 = -b1 * c
            d = gcd a2 (gcd b2 c2)
            m = floor (((sqrt (fromIntegral n)) * (fromIntegral a)
                                + (fromIntegral b)) / (fromIntegral c))

is_square n = n == m * m where
            m = (floor . sqrt . fromIntegral) n

n = 10^4
main = print (length (filter odd (map period
                    (filter (not .is_square) [2..n]))))