Project Euler: Problem 20

n! means n x (n - 1) x ... x 3 x 2 x 1

For example, 10! = 10 x 9 x ... x 3 x 2 x 1 = 3628800,
and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.
Find the sum of the digits in the number 100!

The approach to this problem is quite similar to problem 16 which we can see here. We just need to deal with a really large number here. So, GMP again to the rescue.

library(gmp)

x <- factorialZ(100)

sum(as.numeric(unlist(strsplit(as.character(x), split=""))))

# as.character(x) coverts the big number into a string

# strsplit() extracts individual elements of the string. This can be ensured by using the split = "" argument, which splits the string one element at a time

# strsplit() returns a list. To access the elements of this list, use unlist()

# convert the individual characters to numeric using as.numeric()

# sum the elements

Ans: 648

Project Euler: Problem 16

2¹⁵ = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 2¹⁰⁰⁰?

Handling large numbers or rather, very large numbers, can be a pain at times. But have no fear, for GMP is here.

GMP  makes the solution quite simple.

library(gmp)

x <- as.bigz(2^1000)

# as.bigz() is a function in the gmp library that helps dealing with large numbers quite easily 

This is the approach we take

1. Convert the number to a string so that we can extract the individual elements of the number
2. Extract the individual elements or digits
3. Create a vector of these digits
4. Sum the vector
5. Rejoice

sum(as.numeric(unlist(strsplit(as.character(x), split=""))))

# as.character(x) coverts the big number into a string

# strsplit() extracts individual elements of the string. This can be ensured by using the split = "" argument, which splits the string one element at a time

# strsplit() returns a list. To access the elements of this list, use unlist()

# convert the individual characters to numeric using as.numeric()

# sum the elements

Ans: 1366

Project Euler: problem 6

The sum of the squares of the first ten natural numbers is,

1² + 2² + ... + 10² = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + ... + 10)² = 55² = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 - 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

This is one quite simple.

# Create a vector with the first hundred natural numbers

x.1 <- (1:100)
# Square each element of the vector of natural numbers, i.e, square each natural number and store in another vector
y.1 <- x.1^2
head(y.1)
# Sum the first hundred natural numbers and the squares of each of the first hundred natural numbers and take the difference of these sums
a.1 <- sum(y.1)
b.1 <- (sum(x.1))^2
b.1 - a.1
b.1


Answer: 25164150

After solving a couple of these problems, and after reading some solutions posted by aatrujillo here and here, I realize that my solutions are not general, i.e., they only cater to the problem at hand and hence their scope is very limited. For example, consider the above problem. Had the question asked to do the same analysis on the first 200 natural numbers, I would have to rewrite the entire loop again. I understand that in this case it does not involve much more than changing the size of the x.1 vector, but for a problem that involves more than one loop, it seems to be very "uncool". As a result, I have decided to orient my results towards general solutions and then solve the problem by specifying the parameters. Let's see how that goes. :)

Project Euler: problem 3

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?


This one was quite easy, and much easier in R as it turns out.

The GNU Multi-Precision Library (GMP) is available as a package in R. So the only thing I had to do is install the library. Rest... well... not much...

library(gmp)
factorize(600851475143) 

# The factorize function lists down all the prime factors of the number in the parentheses in ascending order.


Answer: 6857


Well, I understand I did not do much here than just being aware of something called the GMP. Don't blame me, blame them or him. But in due respect for the only concrete language known to humankind (Math not R), I shall try to come up with a more genuine approach.

Project Euler: problem 2

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

# Inititae a vector x with two values 1 and 2, the starting points for the Fibonacci series 

x <- c(1,2)

length(x)

# Take an object "i", with a starting value of 1. 
# This object will be used to as an index for the vector "x". 
# We continue to add# the (n - 1)^th term  and the (n - 2)^th term
# to get the n^th term. 

# This process continues as long as an element of vector x with 
# index value "i" just crosses the 4,000,000 mark.

i <- 1

while (x[i] < 4000000){i <- i + 1

                        x.index <- length(x)

                        x[x.index + 1] <- x[x.index] + x[x.index - 1]}

x

# Sum the even values of the Fibonacci series thus obtained

sum(x[x %% 2 == 0])


Answer : 4613732

Project Euler: problem 1

To be fairly honest (assuming there are degrees of honesty), I do know a little about math and programming but I don't know much math or any programming. I've loved math for a long time, but started to learn and understand fairly recently. So during the process of learning and understanding math and a little bit of programming, Shreyes and I thought of sharing our procedures. Most of these procedures aren't the most elegant solutions and at times are plain clumsy and inefficient. We plan to improve our programming skills as we go along.

We have recently started with Project Euler problems and will be posting some of the methods that we have used to arrive at a solution for each of the problems. We know only one language, R and hence our solutions are written in R.

So let's start with problem 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.

I tried two approaches to solve this problem and have detailed both of them below. By the time I was through with the problem, I found another approach.

First, let's see the one that I thought was quite efficient.

# Approach 1

# Create an empty vector of desired length where the results of the division will be stored

x.1 <- rep(NA, 999) 

#NA is replicated 999 times

# For each integer from 1 to 999 (we want numbers below 1000), divide the integer # by either 3 or 5 and take the modulus. 

# If the integer, say "i" is completely divisible by either 3 or 5, assign  that value to the ith element of vector x; otherwise assign i'th value of x to equal to zero

for (i in 1:999){

                if (i %% 3 == 0 || i %% 5 == 0) {x.1[i] <- i} else {x.1[i] <- 0}} 

# "%%" is the modulus function, "||" is the symbol for the "or" command, x.1[i] calls the ith element of vector x.1

# Take all the non-zero values of x, i.e. those values for which the integer was perfectly divisible by either 3 or 5 and assign it to a separate vector

y.1 <- x.1[x.1 != 0]

# This assigns all the nonzero rows of vector x.1 to a vector y.1

# Take a summation of these values and this is the desired output.

sum(y.1)

# "sum" finds the sum of all the elements of vector y.1

Answer: 233168

Also, just to make sure that there is no confusion, the ".1" in x.1 and y.1 does not denote anything special, it is merely an assigning convention indicating that the variables were created for the first approach.

# Approach 2

# Take numbers from 1 to 333 and multiply each by 3 to get multiples of 3.

# We only take numbers till 333 because we have to find the sum of multiples of 3 (and 5) that are less than 1000.

x.2 <- 0

for (i in 1:333){x.2[i] <- i*3}

head(x.2) 

# head shows the first few rows of the object

# For multiples of 5, we take numbers till 199 and the last multiple of 5 below 1000 comes to be 995

y.2 <- 0

for (j in 1:199){y.2[j] <- j*5}

head(y.2)

# 15 is a common multiple of 3 and 5, and hence it will get included twice - once when we add the numbers that are multiples of 3 and once when we add numbers that are multiples of 5. So we need to subtract these 15 and its multiples.

z.2 <- 0

for (k in 1:66){z.2[k] <- k*15}

head(z.2)

# Final sum

sum(x.2) + sum(y.2) - sum(z.2)

Answer: 233168

There is another approach, which uses the funda of arithmetic progressions. Let's see if you can figure that out. 

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.