Problem: Euler task 1

From Euler project, task 1.


"If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000."


Pretty Simple:

(1 to 1000).filter( x => (x %3 == 0) || ( x%5 == 0) ).

            foldLeft(0)(_ + _)

or:

(1 to 1000).foldLeft(0)

   ( (x,y) => x + (if (y % 3 == 0 || y % 5 ==0) y else 0))

The first looks better since the addition is only done when the number is divided by 3 or 5. The second one always executes the addition and the comparison.

However, the first one creates the list of number divided by 3 or 5 first before folding.

So, I think that the second version is better in term of number of created list.

Anyway, I think the following is the best one:

(1 to 1000 / 3).foldLeft(0)( _ + _ * 3) + 

(1 to 1000 / 5).foldLeft(0)( _ + _ * 5) -
(1 to 1000 / 15 ).foldLeft(0)( _ + _ *15)

The first two versions execute 1000 comparisons inside the (1 to ...) , while the second has no comparison. So, I believe the last version should be better than the first two.


In conclusion, my guess of the best performing implementation is the following:
1. Third implementation.
2.  Second implementation.
3.  First implementation.

Maybe the first implementation performs better than the second but the first consumes more memory.

Quick profiling on time of average execution , using 1000 000 as limit instead of 1000 in my machine: 
1. First implementation: 130 ms
2. Second implementation: 65 ms
3. Third implementation: 32 ms.

Finally, I found this one as even more better solution:

(1 to 1000 / 3).foldLeft(0)( _ + _ * 3) + (

 1 to 1000/ 5).foldLeft(0)( 

   (x,y) => x + (if (y % 3 ==0) 0 else (y * 5)))

Any thought ?