Project Euler – Problem1

Problem:

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.

Here is a straight forward solution to this problem,

SELECT SUM(DECODE(MOD(ROWNUM,3),0,ROWNUM,

DECODE(MOD(ROWNUM,5,0,ROWNUM,0)))

FROM DUAL

CONNECT BY LEVEL <1000;

The logic is simple. The CONNECT BY clause in the above statement simply acts as row generator to generate natural numbers from 1 to 999.

The DECODEs inside the aggregate function check whether the number is divisible either by 3 or 5 if so the number is added.

This is a simple solution to understand but certainly not the best when it comes to performance. With the help of mathematical formula this problem can be solved little easier.

Multiples of 3 are 3, 6,9,12 … 999. Sum of them is

3+6+9+…999 = 3 ( 1+2 + … + [999/3]) ( [999/3] denotes integer part of 999/3 )

= 3 ([999/3]) ([999/3]+1)/2 ( 1 + 2+ … + n = n(n+1)/2)

Sum of multiples of 5 is

5 + 10 +15 +…[999/5] = 5([999/5]) ([999/5]+1)/2

The tricky part is the numbers 15, 30 …990 are included in both the case. This series should be subtracted once from the solution. So the final solution is

select trunc(999/3)* (trunc(999/3)+1) *3/2

+ trunc(999/5)* (trunc(999/5)+1) *5/2

- trunc(999/15)* (trunc(999/15)+1) *15/2 from dual;

Answer: 233168