Project Euler 36,37

Problem 36

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

再帰的に10進の回文数を求めて2進でも回文になっているか判定する。2進数の回文数は末尾が1でなければならない。

bin_rev 0 = []

bin_rev n = (mod n 2):(bin_rev (div n 2))

numerize2 a = foldl (\x y -> x * 2 + y) 0 a

is_palindromic2 n = mod n 2 /= 0 && numerize2 (bin_rev n) == n
pali 1 = 0..9

pali 2 = [0,11..99]:(pali 1)

pali n = [ m * k + p * 10 | k <- [0..9], p <- (head (tail a)) ]:a

        where

            m = 10^(n-1) + 1

            a = (pali (n - 1))
n = 6

main = print(sum (filter is_palindromic2 (concat (pali n))))

Problem 37

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

右からと左からの数字の結合で素数性を保つ数の集合を求めていくが、どちらかが空集合になれば終わり。こういうのはzipで簡単に書ける。

primes_temp = 2:[3,5..]

is_prime 1 = False

is_prime n = all (\p -> mod n p /= 0) (takeWhile (\p -> p * p <= n) primes_temp)
exists a n = any (== n) a
num_digits 0 = 0

num_digits n = (num_digits (div n 10)) + 1

add_left n d = d * 10^(num_digits n) + n

trunc_right = [2,3,5,7]:[ filter is_prime

    [ x * 10 + y | x <- a, y <- [1,3,7,9] ] | a <- trunc_right ]

trunc_left = [2,3,5,7]:[ filter is_prime

    [ add_left x y | x <- a, y <- [1..9] ] | a <- trunc_left ]
is_not_empty (a, b) = not (null a) && not (null a)

both_include (a, b) = filter (\n -> exists b n) a

a = takeWhile is_not_empty (zip trunc_right trunc_left)

main = print(sum(filter (> 9) (concat (map both_include a))))