If I'm not wrong :
sum [1..n] = (n² + n)/2
2011/3/30 Daniel Fischer
On Wednesday 30 March 2011 16:39:49, Gilberto Garcia wrote:
Hi Haskellers,
I was solving this problem from project euler to study haskell. I came up whit the following solution and I was wondering if there is a more optimized and concise solution.
Yes. There's a constant-time formula for summing the multiples of k <= a (those are [k, 2*k .. (a `quot` k) * k], so the sum is k* sum [1 .. (a `quot` k)], try to find a formula for sum [1 .. n]), then you need the http://en.wikipedia.org/wiki/Inclusion–exclusion_principle
If you're looking for multiples of any of few numbers, it's very simple then. For longer lists (say you want to sum the multiples of any of 30 numbers), you have to be clever implementing the inclusion-exclusion algorithm to keep the running time low, sometimes other methods may be faster then (fkSum (10^7) [2 .. 30] for example).
fkSum :: Int -> [Int] -> Int fkSum a [] = 0 fkSum a (b) = foldl (+) 0 (filter (\x -> isMultiple x b) [1..a])
isMultiple :: Int -> [Int] -> Bool isMultiple a [] = False isMultiple a (x:xs) = if (mod a x == 0) then True else isMultiple a xs
Thanks in advance ggarcia
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe