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 |
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>
Happy reading !!!
4 comments:
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
Hi Nigel,
How stupid of me.
Thanks for sharing your solution.
Regards
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.
What is it for 1 to 15?
Post a Comment