http://projecteuler.net/index.php?section=problems&id=143 やっと解けた。 import Control.Monad import Data.List import qualified Data.Map as M import qualified Data.IntSet as S eisenstein :: Int -> [(Int,Int)] eisenstein upp = do n <- [1..s…

http://projecteuler.net/index.php?section=problems&id=145 とりあえずナイーブなもの。 import Data.Char revInt ::Integer -> Integer revInt = read.reverse.show reversible n = mod n 10 /= 0 && (all odd.map digitToInt.show.(+n).revInt) n p145 n…

http://projecteuler.net/index.php?section=problems&id=144 一次方程式と二次方程式を解くだけの簡単なお仕事。 だが、計算ミスしそうだったので、慎重にやった。 答えあわない… とおもったら、終了条件を１つ見逃していた。 まったく、これだから英語は。…

身近な人がＴＶにでてた。 １０歳くらい若く見えた。 あんなに変わるもんなんですねぇ。

http://projecteuler.net/index.php?section=problems&id=142 悪いコードである。最小性の保証？何それ、食べられるの？ import Control.Monad import Data.List isSqrt n = (n==).(^2).sqrt'$n sqrt' = floor.sqrt.fromIntegral main = print.head.sort$ p1…

http://projecteuler.net/index.php?section=problems&id=141 とりあえず、ものすごく正直な（愚直ともいう）コード import Data.List divQuotRem n = do d <- [1..n] let (q,r) = divMod n d return [q,d,r] progressive [a,b,c] = let [x,y,z] = sort [a,b…

http://projecteuler.net/index.php?section=problems&id=138 のペル方程式に帰着。 next (x,y) = (9*x+20*y,4*x+9*y) p138 = map snd.iterate next $ (38,17) main = print.sum.take 12$ p138

http://projecteuler.net/index.php?section=problems&id=137 またペル方程式である。結局 をとけばよいことが分かる。で、また、フィボナッチ数が出てくると。 そういう話らしい。 fib = 0:1:zipWith(+) fib (tail fib) nugget = f fib where f (x:y:zs) = …

http://projecteuler.net/index.php?section=problems&id=136とりあえず、100まで調べて 奇素数nに対して、nに対する解が唯一 iff n=3 (mod 4) 奇素数nに対して、4nに対する解は唯一 奇素数nに対して、16nに対する解は唯一 まで分かった。 他の合成数に対し…

http://projecteuler.net/index.php?section=problems&id=135 まず、ナイーブな方法。約数を求めて、利用。 import Data.List divisors n = (1,n):d n 2 where d x m | m^2 > x = [] | mod x m == 0 = (m,div x m):d x (m+1) | otherwise = d x (m+1) sol = …

http://projecteuler.net/index.php?section=problems&id=140 {-- A_G(x) = \frac{x^3 +x}{1-x-x^2} = n D(n) = 5n^2+14n+1 = d^2 X^2-5Y^2=44 X^2-5Y^2=\pm 4 -> X_0=1,Y_0=1 X^2-5Y^2= 11 -> X_0=4,Y_0=1 X^2-5Y^2=-11 -> X_0=3,Y_0=2 --} next (x,y) = (d…

http://projecteuler.net/index.php?section=problems&id=139 {-- X^2+(X+d)^2 = (dY)^2 -> (2X+d)^2-(2d^2)Y^2= -d^2 -> x^2-2y^2 = -1 where X = d*(x-1)/2, Y = y perimeter is X+(X+d)+Y = d(x+y) --} next (x,y) = (3*x+4*y,2*x+3*y) main = print.sum.…

http://projecteuler.net/index.php?section=problems&id=134ユークリッドの互除法を利用。 import Number -- given m,n. find a,b. s.t. am+bn=1 euclid m n | n > m = let (a,b) = euclid n m in (b,a) | r == 1 = (1,-q) | otherwise = let (a,b) = eucli…

http://projecteuler.net/index.php?section=problems&id=131 import Number {-- n^3 + n^2 p = n^2 (n+p) = cube p : prime -> gcd n (n+p) = 1 より n^2 と n+p は共通因数を持たない 従って n = a^3 , n+p = (a+k)^3 とおける ここで (a+k)^3 = a^3 + 3 a…

http://projecteuler.net/index.php?section=problems&id=185 Number Mindという問題らしい。 すなおに実装したら、解けなかった（計算量的な意味で） そこで、数独と同じような感覚で実装。 import Data.Array import Data.List import Data.Char type Cand…

http://projecteuler.net/index.php?section=problems&id=130前問の結果を使えば、楽。 {-# OPTIONS_GHC -XBangPatterns #-} import Number count n = count' n (0,100) 1 count' n (q,r) !k | gcd 10 n /= 1 = n | (q,r)==(0,10) = k | otherwise = count' …

http://projecteuler.net/index.php?section=problems&id=129 これも前に考えたことがある。 111...1 = n*mとする(n {-# OPTIONS_GHC -XBangPatterns #-} import Data.List count n (q,r) !k | gcd 10 n /= 1 = 0 | (q,r)==(0,10) = k | otherwise = count n…

http://projecteuler.net/index.php?section=problems&id=128六角形の絵を描いて考えてみると、調べるべき場所が案外少ないことに気づく。 import Number import Data.Maybe import Control.Arrow top n | all isPrime around = Just $ 2+3*n*(n-1) | otherw…

http://projecteuler.net/index.php?section=problems&id=133 これも同様。 オイラーの定理（だっけ？）と前を利用。 import Number hiding(powMod) powMod a n m | n < 3 = a^n `mod` m | otherwise = let (q,r) = divMod n 2 aq = powMod a q m in aq*aq*a…

http://projecteuler.net/index.php?section=problems&id=132 前と基本は同じ。 nがd桁で循環するなら 10^d=1 (mod n) これを利用。 import Number hiding(powMod) target = 10^9 powMod a n m | n < 3 = a^n `mod` m | otherwise = let (q,r) = divMod n 2 …

http://projecteuler.net/index.php?section=problems&id=126立方体を数える簡単なお仕事、とはいかなく。高速化は結構大変だった。 でいろいろやった結果が下。 import Data.Array.IO import Data.List upper = 50000 layer (h,w,d) n = 4*(h+w+d+n-2)*(n-1…

ghc --make -prof -auto-all -O2 foo.hs ./foo.exe +RTS -p でプロファイル foo.profができる。./foo.exe +RTS -h hp2ps foo.hc でヒープ領域 foo.psができる。

http://projecteuler.net/index.php?section=problems&id=127いまいちぱっとしないコードである。 import Number import Data.List import Data.Array.IArray upper = 110000 rad = listArray (1,upper).map (product.nub.factors) $ [1..upper]::Array Inte…

http://projecteuler.net/index.php?section=problems&id=125nubを忘れてハマッタ。 import Data.List isPalin x=(reverse.show)x==show x sumSquUpTo upp n = takeWhile (

http://projecteuler.net/index.php?section=problems&id=124 これも、そのまま。 import Number import Data.List rad = product.nub.factors p124 m= sort[(rad n,n)|n<-[1..m]] main = print.snd$p124 (10^5) !!9999

http://projecteuler.net/index.php?section=problems&id=123 そのまま。 import Number import Data.List import Control.Monad main =print.liftM (+1).findIndex (>10^10). zipWith remainder primes$ [1..] where remainder p n | odd n = 2*n*p `mod` (…

http://projecteuler.net/index.php?section=problems&id=121確率を計算して、その逆数を求めるかんたんなお仕事 だったが、問題文を理解するのに多大な時間を費やした。 英語 きらいです。 prob m n | n == 0 = 1 | m > n = (prob (m-1) (n-1)+ m*prob (m-1…

http://projecteuler.net/index.php?section=problems&id=119brute force. かなり遅い。もう少し早いものを考えたいが、思いつかない。 import Data.List import Data.Char digits :: Integer -> [Integer] digits = map (toInteger.digitToInt).show p119 n…

http://projecteuler.net/index.php?section=problems&id=122深さ優先。最初は幅優先でやってみたが、どう考えても葉が増えすぎる。 import qualified Data.Map as M import Control.Monad depth = 15 bound = 200 search ::M.Map Int Int -> [Int] -> M.Map…

大方の予想を裏切り、見事完走できました。ほうとうおいしいです。