If I'm not wrong : sum [1..n] = (n² + n)/2
2011/3/30 Daniel Fischer <daniel.is.fisc...@googlemail.com> > 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 >
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
