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