Haskell

Project Euler 100

http://projecteuler.net/index.php?section=problems&id=100 Pell方程式に帰着される。 pells x = (f x):[ f y | y <- pells x ] where f (a,b) = (a * 3 + b * 4, a * 2 + b * 3) solutions = [ (div (b + 1) 2, div (a + 1) 2) | (a,b) <- pells (1,1) ] …

Project Euler 99

http://projecteuler.net/index.php?section=problems&id=99 指数の計算をする代わりにlogの計算をする。

Project Euler 98

http://projecteuler.net/index.php?section=problems&id=98 ペアを作って、桁数が合う平方数すべてについてマッチするか調べる。

Project Euler 97

http://projecteuler.net/index.php?section=problems&id=97 Haskellならそのまま計算できる。 main = print (mod (28433*(2^7830457)+1) (10^10)) これではあんまりなので、なるべく短い桁で計算できるよう、バイナリ法で。 pow_mod n 0 d = 1 pow_mod n m …

Project Euler 96

http://projecteuler.net/index.php?section=problems&id=96 マスに可能な数字を次々に当てはめていき矛盾が無い解を出すだけ。それなりに速い。

Project Euler 95

http://projecteuler.net/index.php?section=problems&id=95 次を配列にしておく。

Project Euler 94

http://projecteuler.net/index.php?section=problems&id=94 Pell方程式に帰着される。 pells m n = (next m n):[ next p q | (p, q) <- pells m n ] where next m n = (m * 2 + n * 3, m + n * 2) limit = 10^9 main = print (sum (takeWhile (<= limit) [ …

Project Euler 93

http://projecteuler.net/index.php?section=problems&id=93 演算子の配列は、 operators = [ (+), (-), (*), (/) ] けれど、実際の演算は、 op = (+) n = op 1 2 -- 3 と、前置にしなければならない。 0割りを回避するところで、演算子が(/)かどうかを直接…

Project Euler 92

http://projecteuler.net/index.php?section=problems&id=92 1000までは1か89になるまで辿って89になればSetに入れる。それより大きい場合は1000以下になるまで辿る。この問題の範囲内では1回で1000以下になるはず。

Project Euler 91

http://projecteuler.net/index.php?section=problems&id=91 点Pを軸上以外に取って、Pを通りOPに垂直に直線を引く。その直線上の格子点がQ。 f n = 3 * n * n + sum [ g (x,y) | x <- [1..n], y <- [1..n] ] g (x,y) = (min (div x dx) (div (n - y) dy)) +…

Project Euler 90

http://projecteuler.net/index.php?section=problems&id=90 組合せを出して判定するだけ。

Project Euler 89

http://projecteuler.net/index.php?section=problems&id=89 1000の位だけ特別扱い。

Project Euler 88

http://projecteuler.net/index.php?section=problems&id=88 雑にSetを使って。コンパイルして最適化オプションつけたら非常に速くなった。

Project Euler 87

http://projecteuler.net/index.php?section=problems&id=87 素直に取りうる値のリストを作ってSetに入れて大きさを見る。 import Data.Set (fromList, size) is_prime n = all (\p -> mod n p /= 0) (takeWhile (\p -> p * p <= n) primes) primes = 2:[ n …

Project Euler 86

http://projecteuler.net/index.php?section=problems&id=86 l(m2 - n2) か 2lmn のどちらかがM。

Project Euler 84

http://projecteuler.net/index.php?section=problems&id=84 基本的にProblem 280と同じだが、圧倒的に複雑。遷移確率を求めて、100回目の分布を計算する。しかし、どこかが間違っているらしい。結果的には正しい答えが出てくるが。 以前はどうやったのかコ…

Project Euler 85

http://projecteuler.net/index.php?section=problems&id=85 Pythonで解いたときと違う方法を採った。2000000, 1999999, 2000001, ...という数に対して三角数の積になっていないか調べる。

Project Euler 81,82,83

http://projecteuler.net/index.php?section=problems&id=81 http://projecteuler.net/index.php?section=problems&id=82 http://projecteuler.net/index.php?section=problems&id=83 3題とも同じアルゴリズムで計算できる。違うのは初期のマスと最小を取る…

Project Euler 80

http://projecteuler.net/index.php?section=problems&id=80 昔習った平方根を1桁ずつ求める計算法をシミュレートする。 square_rootは平方根の精度が1桁ずつよくなるリスト。例えば、 square_root = [1, 14, 141, 1414, 14142, …] その中のaは、余りと答え…

Project Euler 79

http://projecteuler.net/index.php?section=problems&id=79 ものすごくいい加減な解法。数字が右にあるか左にあるか、各ペアで調べる。50個のリストでそれがすべて分かるので、順番が付けられる。

Project Euler 78

http://projecteuler.net/index.php?section=problems&id=78 まともに計算すると遅いので、メモ化する。 コンパイルするときは --makeをつける。それでもPython並みに遅い。 import Data.Map (Map, (!), empty, insert, lookup) n = 10^6 f m 0 = (insert 0 …

Project Euler 77

http://projecteuler.net/index.php?section=problems&id=77 Haskellなら簡単に書ける。 n = 5000 is_prime n = all (\p -> mod n p /= 0) (takeWhile (\p -> p * p <= n) primes) primes = 2:(filter is_prime [3,5..]) mul f p = [ g f k 0 | k <- [0..] ]…

Project Euler 76

http://projecteuler.net/index.php?section=problems&id=76 分割数は母関数を使えば簡単。 n = 100 mul f n = [ g f k 0 | k <- [0..] ] where g (x:xs) k m | k < m = 0 | otherwise = (if mod (k - m) n == 0 then x else 0) + (g xs k (m + 1)) p = fold…

Project Euler 75

http://projecteuler.net/index.php?section=problems&id=75 ピタゴラスの数の生成式を使って周囲の長さをリストにする。例えば60までなら、 [12,24,36,48,60,30,60,40,56] これをMapに入れようとしたが、メモリが足りない。 import qualified Data.Map as M…

Project Euler 74

http://projecteuler.net/index.php?section=problems&id=74 チェーンにパターンがあるのがややこしい。

Project Euler 73

http://projecteuler.net/index.php?section=problems&id=73 速くなる書き方もあるが、ここは題意を素直に表現。 count_numerator d = length (filter (\n -> gcd d n == 1) [(div d 3)+1..div (d-1) 2]) main = print (sum (map count_numerator [1..12000]…

Project Euler 72

http://projecteuler.net/index.php?section=problems&id=72 エラトステネスのふるいがなぜこんなに遅いのか。 import Data.Array make_primes n = filter (a!) [2..n] where a = sieve (array (2, n) [ (k, True) | k <- [2..n] ]) 2 sieve a p | a!p = sie…

Project Euler 71

http://projecteuler.net/index.php?section=problems&id=71 分数を使ってみた。Haskellでの分数の使い方はこんな感じ。 import Ratio a = 2 % 4 -- 1 % 2 n = numerator a -- 1 d = denominator a -- 2 b = 1 / a -- 2 % 1 分母は最後の7つだけ調べればよい…

Project Euler 70

http://projecteuler.net/index.php?section=problems&id=70 pが大きい方から、素数の組(p, q) (p ≤ q)に対し、調べていく。 import Data.List is_prime n = all (\p -> mod n p /= 0) (takeWhile (\p -> p * p <= n) primes) primes = 2:(filter is_prime […

Project Euler 60

http://projecteuler.net/index.php?section=problems&id=60Setが自由に使うのが難しい。しかたがないので、上限を倍々していく。とても遅い。