[Haskell-cafe] For Project Euler #1 isn't it more efficient to generate just the numbers you need? <Spoiler>

[KC]

Got it.

You mean use the formula for summing an arithmetic progression twice
and take account of duplicates.

Sheer genius!


On Sat, May 7, 2011 at 11:56 AM, Eugene Kirpichov <ekirpichov at gmail.com> wrote:
> One doesn't have to touch them to compute their sum.
>
> 2011/5/7 KC <kc1956 at gmail.com>:
>> Do you mean O(1) complexity?
>>
>> Don't you have to touch at least the multiples of 3 & 5 making it O(k)
>> where is the number of multiples of 3 and the number of multiples of
>> 5?
>>
>>
>> On Fri, May 6, 2011 at 10:10 PM, Lyndon Maydwell <maydwell at gmail.com> wrote:
>>> If you're looking for efficiency, I believe you can actually do #1 in
>>> constant time:
>>>
>>>
>>> On Sat, May 7, 2011 at 7:31 AM,  <caseyh at istar.ca> wrote:
>>>> -- Instead of this
>>>> -- sumMultiples3or5 s = sum [x | x <- [3..s-1], x `mod` 3 == 0 || x `mod` 5
>>>> == 0]
>>>>
>>>>
>>>> -- Isn't this faster
>>>>
>>>> sumMultiples3or5 s = sum ([x | x <- [3,6..s-1]] `merge` [x | x <-
>>>> [5,10..s-1]])
>>>>
>>>> merge xs [] = xs
>>>> merge [] ys = ys
>>>> merge txs@(x:xs) tys@(y:ys)
>>>>    | x < y     = x : xs `merge` tys
>>>>    | x > y     = y : txs `merge` ys
>>>>    | otherwise = x : xs `merge` ys
>>>>
>>>>
>>>>
>>>> _______________________________________________
>>>> Haskell-Cafe mailing list
>>>> Haskell-Cafe at haskell.org
>>>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>>>>
>>>
>>> _______________________________________________
>>> Haskell-Cafe mailing list
>>> Haskell-Cafe at haskell.org
>>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>>>
>>
>>
>>
>> --
>> --
>> Regards,
>> KC
>>
>> _______________________________________________
>> Haskell-Cafe mailing list
>> Haskell-Cafe at haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>>
>
>
>
> --
> Eugene Kirpichov
> Principal Engineer, Mirantis Inc. http://www.mirantis.com/
> Editor, http://fprog.ru/
>



-- 
--
Regards,
KC