Project Euler 30,34 - inamori’s diary

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

Problem 30

使う数字を選んで、その5乗和の数字をソートしたら元に戻ればOK。数字は重複組合せになる。これは組合せより少しコードが簡単になる。



import Data.List
rep_comb a 0 = [[]]

rep_comb a n = concat (map (\m -> (map ([m] ++ )

        (rep_comb (filter (\l -> l >= m) a) (n - 1)))) a)
numerize a = foldl (\x y -> x * 10 + y) 0 a

digits 0 = []

digits n = (digits (div n 10)) ++ [mod n 10]
e = 5

sum_pow a = sum (map (^e) a)

is_valid a = sort (digits (sum_pow a)) == a
limit = head (dropWhile (\n -> 9^e * n >= 10^n) [1..])

main = print(sum (map (\n -> 

        sum (map sum_pow (filter is_valid (rep_comb [0..9] n))))

        [2..limit]))

Problem 34

ほとんど同じ。



 -- digitsなどは同じ

factorial 0 = 1

factorial n = n * factorial(n - 1)
sum_fac a = sum (map factorial a)

is_valid a = sort (digits (sum_fac a)) == a
limit = head (dropWhile (\n -> factorial(9) * n >= 10^n) [1..])

main = print(sum (map (\n -> 

        sum (map sum_fac (filter is_valid (rep_comb [0..9] n))))

        [2..limit]))