<div dir="ltr"><div class="gmail_extra"><div><div>Yes, that would work, but this approach will exceeding the time limit of 5 seconds. Keep in mind that this program should process 100.000 numbers which will range from 1 to 1.000.000.000 in under five seconds</div><div><br></div><div>My current implementation it won't succeed regarding the time factor, but I did get some insights, I know where to look now (I guess)!</div><div><br></div><div>Just to illustrate what I am saying: for instance this function</div><div>> sum [3,6..9999999]</div><div>Takes ~1 second to return, and these are just the multiples of 3, to get the real answer I would have to first sum the multiples of 5 and 15...</div></div><div><br></div><div class="gmail_quote">2015-01-27 23:09 GMT-02:00 Animesh Saxena <span dir="ltr"><<a href="mailto:animeshsaxena@icloud.com" target="_blank">animeshsaxena@icloud.com</a>></span>:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div><div>why not just use infinite series. mathematically...<br><br>series 1 = Mutiples of 3 <br>series 2 = Multiples of 5<br>Apply filter and sum to get the answer<span class=""><font color="#888888"><br><br></font></span></div><div><span class=""><font color="#888888">-Animesh</font></span><div><div class="h5"><br>On Jan 27, 2015, at 04:43 PM, Jean Lopes <<a href="mailto:hawu.bnu@gmail.com" target="_blank">hawu.bnu@gmail.com</a>> wrote:<br><br><div><blockquote type="cite"><div><div dir="ltr">Your solution runs really quick! I'll study it. Thank you</div><div class="gmail_extra"><br><div class="gmail_quote">2015-01-27 22:25 GMT-02:00 Lyndon Maydwell <span dir="ltr"><<a href="mailto:maydwell@gmail.com" target="_blank">maydwell@gmail.com</a>></span>:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr">Ah sorry, I didn't notice that you were doing that. The effectiveness of the trick really only comes into play though if you use an analytic solution for finding the sum of the multiples of 3, etc.<div><br></div><div>I haven't tested this code in a while, but here's what I wrote some time ago:</div><div><br></div><div><br></div><div><div>sum2 :: Integer -> Integer -> Integer -> Integer</div><div>sum2 a b ceiling = aX + bX - abX</div><div>where</div><div>aX  = sum1 a ceiling</div><div>bX  = sum1 b ceiling</div><div>abX = sum1 (a * b) ceiling</div><div><br></div><div>sum1 :: Integer -> Integer -> Integer</div><div>sum1 x ceiling = sum1' (even times) times x</div><div>where</div><div>times = ceiling `div` x</div><div><br></div><div>sum1' :: Bool -> Integer -> Integer -> Integer</div><div>sum1' True times x = area</div><div>where</div><div>area = (times + 1) * (times * x) `div` 2</div><div><br></div><div>sum1' False times x = max + area'</div><div>where</div><div>max   = times * x</div><div>area' = sum1' True (times - 1) x</div></div><div><br></div><div><br></div><div>Please excuse the poor Haskell style as it is quite possibly the first Haskell program I ever wrote.</div><div><div><div><br></div><div><br></div><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Jan 28, 2015 at 11:15 AM, Jean Lopes <span dir="ltr"><<a href="mailto:hawu.bnu@gmail.com" target="_blank">hawu.bnu@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr">Thats actually what I did...</div><div class="gmail_extra"><br><div class="gmail_quote">2015-01-27 22:11 GMT-02:00 Lyndon Maydwell <span dir="ltr"><<a href="mailto:maydwell@gmail.com" target="_blank">maydwell@gmail.com</a>></span>:<div><div><br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr">I remember that when I had a look at Euler 1 I found that there's a fun solution that should run in "constant" time.<div><br></div><div>You can find the sum of the multiples of 3, add the multiples of 5, and then subtract the multiples of 3*5.</div><div><br></div><div>Is that the kind of thing you're looking for?</div><div><br></div><div> - Lyndon</div><div><br></div></div><div><div><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Jan 28, 2015 at 10:57 AM, Jean Lopes <span dir="ltr"><<a href="mailto:hawu.bnu@gmail.com" target="_blank">hawu.bnu@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div>I'm not really good at math, maybe I am missing something obvious ?</div><div>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</div></div><div class="gmail_extra"><br><div class="gmail_quote">2015-01-27 21:38 GMT-02:00 Brandon Allbery <span dir="ltr"><<a href="mailto:allbery.b@gmail.com" target="_blank">allbery.b@gmail.com</a>></span>:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Tue, Jan 27, 2015 at 6:29 PM, Jean Lopes <span dir="ltr"><<a href="mailto:hawu.bnu@gmail.com" target="_blank">hawu.bnu@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><span style="font-size:15px;line-height:21.2999992370605px">The problem to be solved: <a href="https://www.hackerrank.com/contests/projecteuler/challenges/euler001" target="_blank">https://www.hackerrank.com/contests/projecteuler/challenges/euler001</a> </span></blockquote></div><span><span><br> </span> </span>It's worth remembering that the Euler problems are all about math understanding; often they are designed such that brute force solutions will time out or otherwise fail.<span><span> <span style="color:rgb(136,136,136)" color="#888888"> <span> <span style="color:rgb(136,136,136)" color="#888888"> <br></span></span></span></span></span><div><br></div><span><span><span style="color:rgb(136,136,136)" color="#888888"><span><span style="color:rgb(136,136,136)" color="#888888">-- <br></span></span></span></span></span><div><div dir="ltr"><div>brandon s allbery kf8nh                               sine nomine associates</div><div><a href="mailto:allbery.b@gmail.com" target="_blank">allbery.b@gmail.com</a>                                  <a href="mailto:ballbery@sinenomine.net" target="_blank">ballbery@sinenomine.net</a><div style="width:0px;min-height:0px"> </div></div><div>unix, openafs, kerberos, infrastructure, xmonad        <a href="http://sinenomine.net" target="_blank">http://sinenomine.net</a><div style="width:0px;min-height:0px"> </div></div></div></div></div></div><span> <span style="color:rgb(136,136,136)" color="#888888"> <br>_______________________________________________<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/mailman/listinfo/beginners</a> <br> <br> </span> </span></blockquote></div><br></div><br>_______________________________________________<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/mailman/listinfo/beginners</a> <br> <br></blockquote></div><br></div></div></div><br>_______________________________________________<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/mailman/listinfo/beginners</a> <br> <br></blockquote></div></div></div><br></div><br>_______________________________________________<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/mailman/listinfo/beginners</a> <br> <br></blockquote></div><br></div></div></div></div><br>_______________________________________________<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/mailman/listinfo/beginners</a> <br> <br></blockquote></div><br></div><div><span>_______________________________________________<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/mailman/listinfo/beginners</a> <br> </span></div></div></blockquote></div></div></div></div></div><br>_______________________________________________<br>
Beginners mailing list<br>
<a href="mailto:Beginners@haskell.org">Beginners@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/beginners" target="_blank">http://www.haskell.org/mailman/listinfo/beginners</a><br>
<br></blockquote></div><br></div></div>