Project Euler 48,49

Haskell

Problem 48

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


剰余を取らなくても瞬時に答えが出た。



n = 1000

s = show (sum [ k^k | k <- [1..n] ])

main = print(reverse (take 10 (reverse s)))

Problem 49

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


重複組合せで4つの数字を出し、それを使った数を順列で出し、頭と末尾でフィルターをかけて、その集合の中から3つを選んで等差数列になっていれば素数判定をする。



import Data.List
is_prime n = all (\p -> mod n p /= 0) (takeWhile (\p -> p * p <= n) [2..])
rep_comb a 0 d = [[]]

rep_comb a n d = concat (map (\m -> (map (\b -> m:b)

                        (rep_comb a (n - 1) m))) (filter (>=d) a))

rep_combinations a n = rep_comb a n 0
combinations a 0 = [[]]

combinations a n = concat (map (\e -> map (e:)

            (combinations (filter (>e) a) (n - 1))) a)
numerize a = foldl (\x y -> x * 10 + y) 0 a
unique [] = []

unique (p:ps) = if notElem p ps then p:(unique ps) else unique ps
is_valid a = (head a) /= 0 && mod d 2 == 1 && d /= 5 where d = (last a)

is_arithmetic [p,q,r] = p + r == q * 2
a = map (filter is_valid) (map permutations (rep_combinations [0..9] 4))

b = filter (\b -> length b >= 4) (map (map numerize) (map unique a))

c = filter is_arithmetic (concat (map (\a -> combinations a 3) b))

d = filter (all is_prime) c

main = print(map (\a -> concat (map show a)) d)