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
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@haskell.org http://www.haskell.org/mailman/listinfo/beginners