# [Haskell-cafe] how to optmize this code?

Yves Parès limestrael at gmail.com
Wed Mar 30 18:04:08 CEST 2011

```If I'm not wrong :

sum [1..n] = (n² + n)/2

2011/3/30 Daniel Fischer <daniel.is.fischer at googlemail.com>

> On Wednesday 30 March 2011 16:39:49, Gilberto Garcia wrote:
> >
> > 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
> >
> > ggarcia
>
> _______________________________________________