Project Euler 52,53

Problem 52

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

6倍しても桁が上がらないことを利用する。

import Data.List

digits 0 = []
digits n = (digits (div n 10)) ++ [mod n 10]

normalize = sort . digits
is_valid n = f n 2 where
        m = normalize n
        f n 7 = True
        f n k | (normalize (n * k)) == m = f n (k + 1)
              | otherwise                = False

a = concat [ [10^(n-1)..div (10^n-1) 6] | n <- [6..] ]
main = print(head (filter is_valid a))

Problem 53

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

すべて計算しても答えは出るが、

c n 0 = 1
c n r = (c n (r - 1)) * (n - r + 1) `div` r

a = concat [ [ c n r | r <- [0..n] ] | n <- [1..100] ]
main = print(length (filter (>10^6) a))

パスカルの三角形の下から攻めて、境界を探したほうが速い。

right c n r = c * (n - r) `div` (r + 1)
left c n r = c * r `div` (n - r + 1)
up c n r = c * (n - r) `div` n

m = 10^6
n0 = 100
(r0,c0) = head (filter (\(n,c) -> c > m) a) where
            a = (0,1):[ (r + 1, right c n0 r) | (r, c) <- a ]

bound_in_row (n,r,c)
        | c1 < m    = head (filter    (\(_,r,c) -> c > m || r * 2 > n) a)
        | otherwise = last (takeWhile (\(_,_,c) -> c > m) b) where
                a = (n,r,c1):[ (n,r+1,right c n r) | (n,r,c) <- a ]
                b = (n,r,c1):[ (n,r-1,left  c n r) | (n,r,c) <- b ]
                c1 = up c (n + 1) r

bound = (n0,r0,c0):[ bound_in_row (n-1,r,c) | (n,r,c) <- bound ]
main = print(sum [ n - r * 2 + 1 | (n,r,_) <-
            (takeWhile (\(n,r,c) -> r * 2 <= n) bound) ])