Haskellの勉強中 - しがないプログラマの日記

現在、Haskellの勉強中です。ちょっと気になる記事があったので、解いてみました。あってるかな？問題は、
$\Large \sum_{i=0}^n n mod i$
を求める $\Large O(n^{\frac{1}{2}})$ のアルゴリズムがあるとのことだったのでそれを考えてみました。

module SumMod where

display n = map (n `mod`) [1..n]
sum n = foldr1 (+) (map (n `mod`) [1..n])

summod :: Integer -> Integer -> Integer
summod n i = let m = (div n i) - (div n (i + 1))
                 k = mod n i
             in i*m*(m-1) `div` 2 + k*m

sum2' :: Integer -> Integer -> Integer
sum2' n i = let m = div n i
            in if m > i
                then summod n i
                else foldr1 (+) (map (n `mod`) [1..m])
sum2 n = foldr1 (+) [sum2' n i | i <- [1..n], i <= div n i + 1]

sum2 がその答えになっているはずです。
sum は普通に計算した場合です。