Problem 239

Project Euler Haskell

239 Twenty-two Foolish Primes
Problem 239 - Project Euler
確率の問題．
ちょっと，混乱した．
22個同じなのか，22個違うのか，とか．
確率は難しいです．
とりあえず3つの素数を固定．
残り，22個が異なる位置になる確率を考えた．
これは，少なくとも一つの素数が同じ位置にある確率が分かれば求まる．
簡単に分かるのは，
少なくとも，注目している素数が同じ位置にある確率．
欲しいのは，どの素数か区別するすることなく，少なくとも一つの素数が同じ位置にある確率．
ということで，和集合の確率が分かれば良いと．

import Data.Ratio (Ratio, (%))

choose :: (Integral a) => a -> a -> a
choose n r = div (product [n-r+1..n]) $ product [1..r]

f :: (Integral a) => a -> a -> a
f p c = sum [ (-1) ^ k * product [1.. p + c - k] * choose p k| k <- [0..p] ]

p239 :: (Integral a) => a -> Ratio a
p239 n = f n 75 * choose 25 n % product [1..100]

main :: IO ()
main = print.realToFrac.p239 $ 22

包除原理を利用．

ようやく全問解くことができた．できれば4月前に達成したかった．
次はどんな問題か楽しみ．