[Haskell-beginners] Project Euler #01 on HackerRank, Performance issue‏

[Arjun Comar]

Jean,
This is going to be a bit tough over email, but here goes.

The main trick here is to realize that you can write the multiples of k as
k*i and sum from 1 to floor(n/k) to get the sum of the multiples of k from
1 to n. For example, the sum of the multiples of 3 can be written as:

    sum(3*i, 1, n / 3)

Because of distributivity, we can pull the 3 out of the sum and get

    3 * sum(i, 1, n / 3)

which is pretty cool because now we have a sum from 1 to n/3. We can now
apply the formula that gives us the sum of numbers from 1 to m:

    m * (m + 1) / 2

and substitute m = n / 3. This gives us:

    3 * n / 3 * [(n / 3) + 1] / 2

More generally, we can write the sum of the multiples of k as:

    k * n / k * [(n/k) + 1] / 2

and simplify to:

    n/2 * [(n/k) + 1]

Now you can write out the 3 sums in this form and simplify to an analytic
answer for a closed form answer to the problem:

    n/2 * [(n / 3) + 1] + n/2 * [(n/5) + 1] - n/2 * [(n/15) + 1]

Factor out the n/2:

    n/2 * [(n/3) + (n/5) - (n/15) + (1 + 1 - 1)]

We can now give a common base to the n/k fractions and simplify:

    n/2 * [ 5n/15 + 3n/15 - n/15 + 1] = n/2 * [7n/15 + 1]

Which is the closed form solution you were hoping for.

All that said, don't trust my math and work it out by hand for yourself. I
likely made some mistakes through this procedure :).

Thanks,
Arjun

On Wed, Jan 28, 2015 at 6:12 AM, Frerich Raabe <raabe at froglogic.com> wrote:

> On 2015-01-28 00:57, Jean Lopes wrote:
>
>> I'm not really good at math, maybe I am missing something obvious ?
>> Maybe some pointers as of where to start studying math in order to avoid
>> this brute force attempts, at least to help in this particular
>> problem
>>
>
> I'm not too familiar with 'Project Euler', but summing all multiples of 3
> and 5 below some given 'n' made me think: e.g. 16 it
> would be...
>
>     3 + 5 + 6 + 9 + 10 + 12 + 15
>   = 3 + 6 + 9 + 12 + 15 + 5 + 10                    | reordered summands
>   = 3 + 6 + 9 + 12 + 15 + 5 + 10 + 15 - 15          | +15-15 appended to
> prepare factoring out
>   = 3 + 6 + 9 + 12 + 15  + 5 + 10 + 15  - 15        | whitespace for
> readability
>   = 3 * (1+2+3+4+5)      + 5 * (1+2+3)  - 15 * (1)  | factoring out
>
> Now I remembered a trick to get the sum of the first N numbers (I only
> remember it's called "der kleine Gauß" in german):
>
>   1 + 2 + ... + n = (n^2 + n) / 2
>
> Maybe that'll help.
>
> - Frerich
>
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20150128/abddfaa6/attachment.html>