Project Euler: problem 5

Calculate LCM of 'n' consecutive natural numbers using R
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Well I shall hit the nail right on the head and not beat around the bush. I am taking programming lessons on R from my pro bro(Utkarsh Upadhyay) who agreed on teaching me only if I would disseminate my learning(a paranoia all the open-source advocates share). Hence I shall populate the web with another link, which might help other dumb programmers like me.

Question:What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?(Which is essentially the LCM of all the numbers from 1 to 20)

I came across this problem http://projecteuler.net/index.php?section=problems&id=5 here. You can choose any programming language to solve the problems given. I choose R.

My first attempt to solve this:

a <- 20 

c <- 0  
while ( c < 20){   // this loop stops when the value of ‘c’ becomes 20, i.e ‘a’ is divisible by all the numbers from 1 to 20         
            c <- 0         
            n <- 1       
            a <- a + 1 
            while ( n < 21 ){   // check if ‘a’ is divisible by all numbers from 1 to 20      
                        if (a%%n == 0) c <- c + 1
                        n <- n+1
            }
}
print (a)

Brief note on the program above:

What I am essentially doing is checking if the number in the variable ‘a’ is divisible by all the numbers from 1 to 20, if its not then I am incrementing the value of ‘a’ and proceeding again with the loop(first while loop). So I would be checking for all the numbers starting 21 whether they are divisible by all the numbers from 1 to 20 and the program runs till ‘a’ takes the desired value.(which came out to be 232,792,560, after the computation was over).

This was a conservative way of getting the job done. It however took 9 hours of computation to blurt out the answer. Hmmm, well I could live with that number but just out of curiosity I asked Utkarsh if there was anything that I was missing. I just wish I were there to see the expression on his face, it would probably have been that of despair, or could also have been a hysterical laughter, I would never get to know that(sigh, Schrodinger's cat) but nevertheless lets focus on the task at hand. The suggestion Utkarsh gave was to use "recursive functions".

Revised program using recursive function and pro bro's help:

We essentially define 2 function and call one in the other. Its easier when you look at the code:

Defining a function lcm(a,b) and storing the codes in a file "LCM.R":

lcm <- function(a, b) { 

if(a > b) {     # Swap the numbers to keep the smallest number in ‘a’

               a <- a + b 

               b <- a - b

               a <- a - b

               }

i <- 2

comb <- 1

while(i <= a) { 

                      if(a %% i == 0 && b %% i == 0) {    

                      # Accout for all the common factors

                      a <- a / i 

                      b <- b / i

                     # Count common factors only once.

                     comb <- comb * i

                     } 

else {

            # i is not a common factor, carry on to the next number

        i <- i + 1

        } 

}

return (comb * a * b)    # For the non common factors, count all of them

}

A brief note on the above program:

What we have done here is we have defined a function lcm(a,b) as per our convenience and defined it such that it returns the LCM of ‘a’ and ‘b’. The logic used to calculate the LCM is what most of us have already used in class 5^th. Identify the common factors(which would be contained in ‘i’) and then to compute the LCM just use “comb <- comb * i”. Note that whenever I come across a common factor I am dividing both ‘a’ and ‘b’ by ‘i’ thus the values of ‘a’ and ‘b’ left in the end of the loop would be co-prime.(Think about this.!!). Therefor I am returning (comb * a * b), which would return the LCM of ‘a’ and ‘b’.

This program would be stored in a file let’s say “LCM.R”. Now whenever I have to refer to this function lcm(a,b) all I need to do is source this file “LCM.R” and I can conveniently use the function lcm(a,b) to get the LCM of ‘a’ and ‘b’. It would be as if the function lcm(a,b) always existed.

Now I can address a question for the novice programmers. Where do the 'a' and 'b' come from? 

So whenever I use this self defined function lcm(a,b) I will use it in a program right.? so if I write 

source('LCM.R') // this would allow you to use the function you defined in "LCM.R"

l <- lcm(6,8) // the value of 'a' would be 6 and 'b' would be 8

print (l)

I would get 24.

Defining another function lcm1(list.num) and storing the codes in "LCM2.R"

Now we come to the tricky part. What we will do now is use the function lcm(a,b), that we defined, and use it to compute LCM of a list of numbers.

source('LCM') //calling the file that stores the function lcm(a,b)

lcm1 <- function(list.num) {

                                          LCM.so.far <- 1

                                          for(next.number in list.num) {

                                                             LCM.so.far <- lcm(LCM.so.far, next.number) // Here lies the beauty

                                                                                      }

                                           return (LCM.so.far)

                                          }

A brief about the above program:

What we have done above is defined another function lcm1(list.num) which will take a list of numbers and blurt out the LCM.(Which is exactly what we want.!!). If we look at the ‘for’ loop defined we are running the loop for all the values in the list of numbers. Now the beautiful logic is in the line “LCM.so.far <- lcm(LCM.so.far, next.number)”, we have cleverly used the function defined earlier lcm(a,b) here. LCM.so.far would keep on updating it self as the loop runs with the next number in the list. Finally this function returns the LCM of the list of numbers that would be stored in ‘LCM.so.far’ at the end of the loop.(Think why.!!)

Now this function lcm1(list.num) and its definition would be stored in another file say “LCM2.R”. Similar to how we used the file “LCM.R” to use the function lcm(a,b) we can now source “LCM2.R” to use the function lcm1(list.num) that we defined.!!

So basically we have 2 function defined in 2 different files. To use the functions wll we need to do is source the files they are stored in.

Main Program:

source('LCM2') // this will call both the files(think why.!!)

l <- lcm1(1:20)

print (l)

Here we have sourced the file “LCM2.R” which would automatically open “LCM.R” too, since “LCM2.R” has to use lcm(a,b) defined in “LCM.R”(hope you catch the drift). Now we stored the LCM of the list of numbers from 1 to 20 (1:20) in ‘l’ and displayed ‘l’.

and TADA.!!!

The approximate computation time is <1 sec. And also we get a flexible functionality to compute the LCM of any consecutive list of natural numbers however long(not literally.!!)

Even if I consider that the computation took 1 sec, the program that I came up with took 9*60*60= 32,400 secs. Therefore the approximate efficiency enhancement achieved via this transition is 32,39,900% which is not bad I say..:-)

Critiques, abuses, banters, blessings are welcome. 

P.S: Pardon me for the poor presentation and grammatical errors if any.