Problem 21

http://projecteuler.net/index.php?section=problems&id=21

d(n)をnの割きれる数の合計とする。
このとき、1〜9,999の間で d(n) = m かつ d(m) == n かつ m /= nとなる数の合計を求めよ.

import Data.List
import Data.Array
import Prime

main = print $ sum $ [a | a <- [2..n], isAmcable a]
    where n = 10000
          isAmcable a = let b = (d ! a) in let c = d ! b in b <= n && c == a && b /= a
          d = listArray (1, n) [sum $ init $ g $ f $ divisors i | i <- [1..]]
          divisors n = [] : (groupBy (==) $ map fromIntegral $ primeFactors n)
          f xs = map (scanl (*) 1) xs
          g []       = []
          g [xs]     = xs
          g (xs:xss) = [ x * y | x <- xs, y <- g xss]

let .. in let ... in はちょっとやだな。名前つけるのむずいな。

groupBy (==) て groupじゃん(2008-06-10)。