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. You can find the sum of the multiples of 3, add the multiples of 5, and then subtract the multiples of 3*5. Is that the kind of thing you're looking for? - Lyndon On Wed, Jan 28, 2015 at 10:57 AM, 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

2015-01-27 21:38 GMT-02:00 Brandon Allbery :

...

On Tue, Jan 27, 2015 at 6:29 PM, Jean Lopes wrote:

...

The problem to be solved: https://www.hackerrank.com/contests/projecteuler/challenges/euler001

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.

-- brandon s allbery kf8nh sine nomine associates allbery.b@gmail.com ballbery@sinenomine.net unix, openafs, kerberos, infrastructure, xmonad http://sinenomine.net

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

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. I haven't tested this code in a while, but here's what I wrote some time ago: sum2 :: Integer -> Integer -> Integer -> Integer sum2 a b ceiling = aX + bX - abX where aX = sum1 a ceiling bX = sum1 b ceiling abX = sum1 (a * b) ceiling sum1 :: Integer -> Integer -> Integer sum1 x ceiling = sum1' (even times) times x where times = ceiling `div` x sum1' :: Bool -> Integer -> Integer -> Integer sum1' True times x = area where area = (times + 1) * (times * x) `div` 2 sum1' False times x = max + area' where max = times * x area' = sum1' True (times - 1) x Please excuse the poor Haskell style as it is quite possibly the first Haskell program I ever wrote. On Wed, Jan 28, 2015 at 11:15 AM, Jean Lopes wrote:

Thats actually what I did...

2015-01-27 22:11 GMT-02:00 Lyndon Maydwell :

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.

You can find the sum of the multiples of 3, add the multiples of 5, and then subtract the multiples of 3*5.

Is that the kind of thing you're looking for?

- Lyndon

On Wed, Jan 28, 2015 at 10:57 AM, 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

2015-01-27 21:38 GMT-02:00 Brandon Allbery :

...

On Tue, Jan 27, 2015 at 6:29 PM, Jean Lopes wrote:

...

The problem to be solved: https://www.hackerrank.com/contests/projecteuler/challenges/euler001

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.

-- brandon s allbery kf8nh sine nomine associates allbery.b@gmail.com ballbery@sinenomine.net unix, openafs, kerberos, infrastructure, xmonad http://sinenomine.net

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

why not just use infinite series. mathematically... series 1 = Mutiples of 3  series 2 = Multiples of 5 Apply filter and sum to get the answer -Animesh On Jan 27, 2015, at 04:43 PM, Jean Lopes wrote:

Your solution runs really quick! I'll study it. Thank you

2015-01-27 22:25 GMT-02:00 Lyndon Maydwell :

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.

I haven't tested this code in a while, but here's what I wrote some time ago:

sum2 :: Integer -> Integer -> Integer -> Integer sum2 a b ceiling = aX + bX - abX where aX = sum1 a ceiling bX = sum1 b ceiling abX = sum1 (a * b) ceiling

sum1 :: Integer -> Integer -> Integer sum1 x ceiling = sum1' (even times) times x where times = ceiling `div` x

sum1' :: Bool -> Integer -> Integer -> Integer sum1' True times x = area where area = (times + 1) * (times * x) `div` 2

sum1' False times x = max + area' where max = times * x area' = sum1' True (times - 1) x

Please excuse the poor Haskell style as it is quite possibly the first Haskell program I ever wrote.

On Wed, Jan 28, 2015 at 11:15 AM, Jean Lopes wrote:

Thats actually what I did...

2015-01-27 22:11 GMT-02:00 Lyndon Maydwell :

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.

You can find the sum of the multiples of 3, add the multiples of 5, and then subtract the multiples of 3*5.

Is that the kind of thing you're looking for?

- Lyndon

On Wed, Jan 28, 2015 at 10:57 AM, 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

2015-01-27 21:38 GMT-02:00 Brandon Allbery :

On Tue, Jan 27, 2015 at 6:29 PM, Jean Lopes wrote:

The problem to be solved: https://www.hackerrank.com/contests/projecteuler/challenges/euler001

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.

-- brandon s allbery kf8nh sine nomine associates allbery.b@gmail.com ballbery@sinenomine.net

unix, openafs, kerberos, infrastructure, xmonad http://sinenomine.net

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

sum [3,6..9999999] Takes ~1 second to return, and these are just the multiples of 3, to get

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 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)! Just to illustrate what I am saying: for instance this function the real answer I would have to first sum the multiples of 5 and 15... 2015-01-27 23:09 GMT-02:00 Animesh Saxena :

why not just use infinite series. mathematically...

series 1 = Mutiples of 3 series 2 = Multiples of 5 Apply filter and sum to get the answer

-Animesh

On Jan 27, 2015, at 04:43 PM, Jean Lopes wrote:

Your solution runs really quick! I'll study it. Thank you

2015-01-27 22:25 GMT-02:00 Lyndon Maydwell :

...

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.

I haven't tested this code in a while, but here's what I wrote some time ago:

sum2 :: Integer -> Integer -> Integer -> Integer sum2 a b ceiling = aX + bX - abX where aX = sum1 a ceiling bX = sum1 b ceiling abX = sum1 (a * b) ceiling

sum1 :: Integer -> Integer -> Integer sum1 x ceiling = sum1' (even times) times x where times = ceiling `div` x

sum1' :: Bool -> Integer -> Integer -> Integer sum1' True times x = area where area = (times + 1) * (times * x) `div` 2

sum1' False times x = max + area' where max = times * x area' = sum1' True (times - 1) x

Please excuse the poor Haskell style as it is quite possibly the first Haskell program I ever wrote.

On Wed, Jan 28, 2015 at 11:15 AM, Jean Lopes wrote:

...

Thats actually what I did...

2015-01-27 22:11 GMT-02:00 Lyndon Maydwell :

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.

You can find the sum of the multiples of 3, add the multiples of 5, and then subtract the multiples of 3*5.

Is that the kind of thing you're looking for?

- Lyndon

On Wed, Jan 28, 2015 at 10:57 AM, 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

2015-01-27 21:38 GMT-02:00 Brandon Allbery :

...

On Tue, Jan 27, 2015 at 6:29 PM, Jean Lopes wrote:

> The problem to be solved: > https://www.hackerrank.com/contests/projecteuler/challenges/euler001

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.

-- brandon s allbery kf8nh sine nomine associates allbery.b@gmail.com ballbery@sinenomine.net

unix, openafs, kerberos, infrastructure, xmonad http://sinenomine.net

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

@Arjun Comar: I would like this walkthrough! 2015-01-27 22:37 GMT-03:00 Brandon Allbery :

On Tue, Jan 27, 2015 at 8:33 PM, Jean Lopes wrote:

...

...

sum [3,6..9999999] Takes ~1 second to return, and these are just the multiples of 3, to get

Just to illustrate what I am saying: for instance this function the real answer I would have to first sum the multiples of 5 and 15...

Yes, and what people are telling you is how to do this without generating and iterating through the list, just using the description of it. This is the key to Euler problems; you're using the brute force solution, not the math that lets you skip the slow part and get the answer immediately.

(I've been keeping quiet because I'm not very good at this kind of math myself; I just recognize that Euler problems are always looking for it and that almost any time you find yourself iterating through a generated list of numbers, you're doing it wrong. Even in the cases where you *do* need to do so, there's usually some math that will cut the search space down considerably; you'll run into this if you do one of the Euler problems involving prime numbers, most likely.)

-- brandon s allbery kf8nh sine nomine associates allbery.b@gmail.com ballbery@sinenomine.net unix, openafs, kerberos, infrastructure, xmonad http://sinenomine.net

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

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

Well I did it pretty dirty, not trying to simplify my solution (I'm skeptic of "k * n/k = n" given that this "n / k" is really "floor (n / k)" ... does this really work for you ?), this gave me : import Control.Monad (replicateM_) main = do t <- readLn replicateM_ t (readLn >>= print . pe1 . subtract 1) pe1 n = ( (3 + m3 * 3) * m3 + (5 + m5 * 5) * m5 - (15 + m15 * 15) * m15 ) `quot` 2 where m3 = n `quot` 3 m5 = n `quot` 5 m15 = n `quot` 15 Note that the sum of multiples of 3/5/15 can be seen as a sum of terms of an arithmetic sequence which is always "number of terms * (first term + last term) / 2", easily proven by the expedient of writing the sequence twice : one in the right order and the other in reverse under it, you then see that the sum of two term in column is always the same so ... -- Jedaï