On Wednesday 30 March 2011 16:39:49, Gilberto Garcia wrote:Yes. There's a constant-time formula for summing the multiples of k <= a
> 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.
(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