Monday, March 03, 2008

What is the smallest number divisible by each of the numbers 1 to 20?

This question appeared on Project Euler. I thought of giving it a try using PL/SQL. Before I started to code, I thought of simplifying so that I can reach to the solution in most efficient way.

Any number which is divisible 20 is also divisible by 10, 5 and 1. Similarly, any number divisible by 18 is also divisible by 9. Following is the list of numbers:

Number

Divisible by

20

10, 5, 1

18

9, 1

16

8, 4, 2, 1

14

7, 1

12

6, 3, 2, 1

10

5, 1

8

4, 2, 1

6

3, 2, 1

4

2, 1

Any number divisible by 11 through 20 is also divisible by 1 through 10. So, basically we need to find a number which is divisible by all the number starting from 11 to 20.

We can easily write a PL/SQL code for this, but by what number should the loop increment by. Logically, any number which is divisible by each of the numbers 11 to 20 should be a multiple of 20. So, we need to increment by loop by 20.

Now that the problem is simplified, we can start our PL/SQL code.

SQL> set serveroutput on

SQL>

SQL> set timing on

SQL>

SQL> Declare

2 l_Result Boolean := FALSE;

3 l_Incr Number := 20;

4 l_Solution Number := 0;

5 Begin

6 while NOT l_Result loop

7 l_Solution := l_Solution + l_Incr;

8 If Mod(l_Solution, 11) = 0 And

9 Mod(l_Solution, 12) = 0 And

10 Mod(l_Solution, 13) = 0 And

11 Mod(l_Solution, 14) = 0 And

12 Mod(l_Solution, 15) = 0 And

13 Mod(l_Solution, 16) = 0 And

14 Mod(l_Solution, 17) = 0 And

15 Mod(l_Solution, 18) = 0 And

16 Mod(l_Solution, 19) = 0 And

17 Mod(l_Solution, 20) = 0 Then

18 l_Result := TRUE;

19 End If;

20 end loop;

21 Dbms_output.put_line('Iterations : ' || l_Solution/l_Incr);

22 Dbms_output.put_line('Smallest Number is : ' || l_Solution);

23 End;

24 /

Iterations : 11639628

Smallest Number is : 232792560

PL/SQL procedure successfully completed.

Elapsed: 00:00:10.98

SQL>

“232792560” is the smallest number which is divisible by each of the numbers 1 to 20 and to reach to the solution we performed “11639628” iterations.

Please share your views, if you think we can further simply or optimize this problem and reach to an efficient solution.

Happy reading !!!

4 comments:

Nigel said...

Rather than doing 11.6M iterations why not:

- find prime factors of each number - you nearly did this

- take the smallest necessary collection of those prime numbers (the highest power of each prime)

- multiply them up

And bingo: you have:

2*2*2*2 * 3*3 * 5 * 7 * 11 * 13 * 17 * 19 = 232,792,560

Finding prime factors is easy, and I think this would be more scalable

Regards Nigel

Asif Momen said...

Hi Nigel,

How stupid of me.

Thanks for sharing your solution.

Regards

Anonymous said...

I suggest the same as Nigel.
But an even quicker way is just to think about every prime from 1 to 20.
2*2*2*2=16<20 but 2*2*2*2=32>20,
3*3=9<20 but 3*3*3=27>20
and even easier from 5 to 19.

So, there are numbers which include 4 times the factor 2, but there can not possibly be 5 of them in any number <20.
That is why your number must have 2^4 as a factor, 3^2, 5^1 and so on.

Greetings. Der Schuh.

Anonymous said...

What is it for 1 to 15?