Problem 239

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 <- [..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月前に達成したかった.

次はどんな問題か楽しみ.

More Reading
Newer// Problem 238
Older// mail forward