http://projecteuler.net/index.php?section=problems&id=68 ライブラリのpermutationsでは降順に並べられないので、自作。 やたらにメモリを食って帰ってこなくなるので、コンパイルしたらすぐに返ってくるようになった。順列を出す途中で枝刈りしているん…

Problem 67 http://projecteuler.net/index.php?section=problems&id=67 上から順に計算していく。上に前と後ろどちらかに0を付加して加算する。 3 3 0 0 3 7 4 7 4 7 4 -> 11 4 7 7 11 7 add a b = [ m + n | (m, n) <- zip a b ] next a b = [ max m n | (…

Problem 65 http://projecteuler.net/index.php?section=problems&id=65 連分数の計算法を適用する。最初に1を付加すると計算しやすい。 digits 0 = [] digits n = (mod n 10):(digits (div n 10)) a = 2:1:2:1:[ if n == 1 then 1 else n + 2 | n <- tail a…

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 …

http://projecteuler.net/index.php?section=problems&id=62 Haskellで辞書は次のように使う。 import qualified Data.Map as M m = M.insert 1 2 M.empty n = m M.! 1 -- 2 b = M.member 1 m -- True 3乗して各桁の数字を降順に並べて数にする。同じ数にな…

http://projecteuler.net/index.php?section=problems&id=61 Arrayで有向グラフを作る。

http://projecteuler.net/index.php?section=problems&id=59 3分割して、それぞれ最頻の数を選んで、それはスペースだとみて、キーを作る。

Problem 57 http://projecteuler.net/index.php?section=problems&id=57 時間がかかるのは桁数のカウント。 num_digits 0 = 0 num_digits n = 1 + (num_digits (div n 10)) a = take 1000 ((1,1):[ (p + q * 2, p + q) | (p, q) <- a ]) main = print (lengt…

Problem 55 http://projecteuler.net/index.php?section=problems&id=55 特になにもない。 digits 0 = [] digits n = (digits (div n 10)) ++ [mod n 10] numerize a = foldl1 (\x y -> x * 10 + y) a rev = numerize . reverse . digits is_palindromic n =…

http://projecteuler.net/index.php?section=problems&id=54 カスタムのソートはsortByを使う。 import Data.List a = [ 3, 1, 4, 1, 5 ] b = sort a -- [1,1,3,4,5] c = zip [1..] a d = sortBy cmp c -- [(2,1),(4,1),(1,3),(3,4),(5,5)] cmp (n1,m1) (n2,…

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 = …

Problem 50 http://projecteuler.net/index.php?section=problems&id=50 2から始まる系列、3から始まる系列、をリストにして、長いものから調べていく。遅い。 import Data.Array sieve a p | a!p == True = sieve (a // [ (m, False) | m <- b, a!m ]) (p +…

Problem 48 http://projecteuler.net/index.php?section=problems&id=48 剰余を取らなくても瞬時に答えが出た。 n = 1000 s = show (sum [ k^k | k main = print(reverse (take 10 (reverse s))) Problem 49 http://projecteuler.net/index.php?section=prob…

http://projecteuler.net/index.php?section=problems&id=47 順に素因数分解すれば答えは出る。 is_prime n = all (\p -> mod n p /= 0) (takeWhile (\p -> p * p <= n) primes) primes = 2:(filter is_prime [3,5..]) div_pow n p | mod n p /= 0 = (n, 0) …

Problem 45 http://projecteuler.net/index.php?section=problems&id=45 六角数は三角数なので、三角数は無視できる。五角数と六角数を並べて比較していくだけ。 polygonal p = [ div (n * ((p - 2) * n - (p - 4))) 2 | n equal (p:ps) (h:hs) | p == h = […

http://projecteuler.net/index.php?section=problems&id=44 まず、できるだけ数学を使わない方法で書いた。Plをlが小さいほうから調べ、Pkとの和が五角数であるものを探す。ただし、kはPk+1-Pk ≤ Plを満たす限り。その中でPl + 2Pkが五角数であるものを探す…

http://projecteuler.net/index.php?section=problems&id=43 ライブラリで順列を出して判定すると非常に遅い。 import Data.List primes = [2,3,5,7,11,13,17] numerize a = foldl (\x y -> x * 10 + y) 0 a is_valid a [] = True is_valid a (p:ps) = if mo…

http://projecteuler.net/index.php?section=problems&id=42 三角数の判定は、 (n2 + n) / 2 = m n2 + n - 2m = 0 n = (-1 + √(1 + 8m)) / 2 だから、1 + 8mが平方数かどうか。 sqrtが使えるが、sqrtの引数は実数でなければならないので型変換する必要がある…

Problem 40 http://projecteuler.net/index.php?section=problems&id=40 こんないい加減な書き方でも意外と速い。実際にはリストを作っていないようだ。 s [] = "" s (p:ps) = (show p) ++ (s ps) mul :: [Char] -> [Int] -> Int -> Int mul s [] k = 1 mul …

Problem 38 http://projecteuler.net/index.php?section=problems&id=38 nで分ける。そのとき左辺第一項をmとして、mの範囲が決まる。例えば、n=4なら、右辺は最初の2つは3桁で残りは2桁だから、 2m ≥ 100, 3m < 100 => 34 ≤ m ≤ 50 range n = if k < n then…

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)) numerize…

Problem 33 http://projecteuler.net/index.php?section=problems&id=33 11の倍数はダメ。 is_cancellable (x, y) = f x y || f y x where f x y = (div y 10) == (mod x 10) && x * (mod y 10) == y * (div x 10)a :: [(Int,Int)] a = filter is_cancellabl…

Problem 31 http://projecteuler.net/index.php?section=problems&id=31 使う最大のコインが決まっているときの総額の作り方の場合の数の配列をリストにする。 ちょっとややこしくなるとなかなか書けない。

http://projecteuler.net/index.php?section=problems&id=30 Problem 30 使う数字を選んで、その5乗和の数字をソートしたら元に戻ればOK。数字は重複組合せになる。これは組合せより少しコードが簡単になる。 import Data.Listrep_comb a 0 = [[]] rep_comb …

http://projecteuler.net/index.php?section=problems&id=29 重複を排除するためにsetを用いる。setの使用は次のように行う。 import qualified Data.Set as Sinsert s n = S.insert n s s = S.empty s2 = S.insert 1 s b = S.member 1 s2 s3 = S.delete 1 s…

http://projecteuler.net/index.php?section=problems&id=28 螺旋を1歩ずつ辿っていくとこう書ける。ただし、遅い。 n = 1001 next (x, y) | y >= 0 && y >= abs(x) = (x + 1, y) | x = abs(y) = (x, y + 1) | y = abs(x) = (x - 1, y) | otherwise = (x, y …

Problem 25 http://projecteuler.net/index.php?section=problems&id=25 単に桁数を求めると遅いが、桁数は数列の前の項のそれと同じかそれより1大きいかなので、それを考慮すると速くなる。 -- number of digits of n is m or m + 1 num_digits n m = if n …

http://projecteuler.net/index.php?section=problems&id=24 例えば、0〜3で10番目の順列を考える。先頭の数字を選ぶと残りは3!通りだから、9を6で割ると1で余りは3。同様に2!で割って1余り1。1!で割って1余り0。これで[1,1,1,0]というリストができる。そこ…

Problem 22 http://projecteuler.net/index.php?section=problems&id=22 ファイルからテキストを読むにはreadFileを使う。 文字をアスキーコードにするにはChar.ordを使う。 switch文のようなcase式がある。 import Data.List import Charsplit_core buff []…

Problem 22 http://projecteuler.net/index.php?section=problems&id=22 ファイルからテキストを読むにはreadFileを使う。 文字をアスキーコードにするにはChar.ordを使う。 switch文のようなcase式がある。 import Data.List import Charsplit_core buff []…