<div dir="ltr">Jean,<br>This is going to be a bit tough over email, but here goes.<br><br>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:<br><br> sum(3*i, 1, n / 3)<br><br>Because of distributivity, we can pull the 3 out of the sum and get<br><br> 3 * sum(i, 1, n / 3)<br><br>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:<br><br> m * (m + 1) / 2<br><br>and substitute m = n / 3. This gives us:<br><br> 3 * n / 3 * [(n / 3) + 1] / 2<br><br>More generally, we can write the sum of the multiples of k as:<br><br> k * n / k * [(n/k) + 1] / 2<br><br>and simplify to:<br><br> n/2 * [(n/k) + 1]<br><br>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:<br><br> n/2 * [(n / 3) + 1] + n/2 * [(n/5) + 1] - n/2 * [(n/15) + 1]<br><br>Factor out the n/2:<br><br> n/2 * [(n/3) + (n/5) - (n/15) + (1 + 1 - 1)]<br><br>We can now give a common base to the n/k fractions and simplify:<br><br> n/2 * [ 5n/15 + 3n/15 - n/15 + 1] = n/2 * [7n/15 + 1]<br><br>Which is the closed form solution you were hoping for.<br><br>All that said, don't trust my math and work it out by hand for yourself. I likely made some mistakes through this procedure :).<br><br>Thanks,<br>Arjun <br></div><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Jan 28, 2015 at 6:12 AM, Frerich Raabe <span dir="ltr"><<a href="mailto:raabe@froglogic.com" target="_blank">raabe@froglogic.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">On 2015-01-28 00:57, Jean Lopes wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
I'm not really good at math, maybe I am missing something obvious ?<br>
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<br>
problem<br>
</blockquote>
<br></span>
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<br>
would be...<br>
<br>
3 + 5 + 6 + 9 + 10 + 12 + 15<br>
= 3 + 6 + 9 + 12 + 15 + 5 + 10 | reordered summands<br>
= 3 + 6 + 9 + 12 + 15 + 5 + 10 + 15 - 15 | +15-15 appended to prepare factoring out<br>
= 3 + 6 + 9 + 12 + 15 + 5 + 10 + 15 - 15 | whitespace for readability<br>
= 3 * (1+2+3+4+5) + 5 * (1+2+3) - 15 * (1) | factoring out<br>
<br>
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):<br>
<br>
1 + 2 + ... + n = (n^2 + n) / 2<br>
<br>
Maybe that'll help.<span class="HOEnZb"><font color="#888888"><br>
<br>
- Frerich</font></span><div class="HOEnZb"><div class="h5"><br>
<br>
______________________________<u></u>_________________<br>
Beginners mailing list<br>
<a href="mailto:Beginners@haskell.org" target="_blank">Beginners@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/beginners" target="_blank">http://www.haskell.org/<u></u>mailman/listinfo/beginners</a><br>
</div></div></blockquote></div><br></div>