madhavkumar2005/project_euler_vaio.R

## project_euler_vaio.R
###### Project Euler ########


# 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.

# Approach 1

# Replicate an empty vector of length where the results of the division
# will be stored
x.1 <- rep(NA, 999)

# For each integer from 1 to 1000, divide the integer by either 3 or 5 and take
# the modulus. If the integer is completely divisible by either 3 or 5, assign
# the i'th value of x that particular integer; otherwise assign i'th value of x
# zero
for (i in 1:999){
                if (i %% 3 == 0 || i %% 5 == 0) {x.1[i] <- i} else {x.1[i] <- 0}
}

# 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]

# Take a summation of these values and this is the desired output.
sum(y.1)


# 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)


# 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 multuples.
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)


###############################################################################


# 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 a vector object "i", with a starting value of 1. This vector 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 nth term. This process continues as long as
# 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])


###############################################################################


# Problem 3

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

# One approach is to use the R function "factorize()" available in the
# gmp library
library(gmp)
factorize(600851475143)

# Logic still needs to be found


################################################################################


# Problem 4

# A palindromic number reads the same both ways.
# The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 x 99.
# Find the largest palindrome made from the product of two 3-digit numbers.

# This problem requires a bit of brainstorming.
# To describe simply, I have taken a two part approach here:
# 1 Generate a list of all Palindromes (within a range),
# 2 Generate a list of all the products of two three digit numbers,
# Try to find the maxmimum match between the two.

# Let's start with part 1.
# Now, a property of all even Palindromes is that they are divisble by 11
# And, since we have to find the largest number here, we can make a safe
# assumption that the number would be a six digit number.
# Then writing the generic form for decimal numbers and using the properties of
# Palindromes, we can create a list of all six digit Palindromes.
palin <- 0
for (a in 1:9){
              for (b in 0:9){
                            for (c in 0:9){
                                          t <- 11*(9091*a + 910*b + 100*c)
                                          palin <- c(palin,t)}}}

palin <- palin[-1] # To remove the initial zero we had assigned to Palin

# It will be easier to match if the list of Palindromes were sorted in a descending
# manner
palin <- rev(palin)
head(palin)


# Now we create a vector of the all the numbers that are product of 2 three digit
# numbers. However, since we know that the Palindrome must be a multiple of 11,
# we can act wise and save some time by creating a vector that is a product of
# 2 three digit numbers but only those which are a multiple of 11.

# Also, it more convenient if we start backwards and go down.
x <- 999
y <- 990
product <- 0
z <- 990

# 110 is the smallest three digit number that is a multiple of 11.
# Here, we arfe creating a vector that has all the three digit multiples of 11.
# We will then multiply each element of this vector to each three digit number.

while (y > 110){y <- y - 11
                z <- c(z,y)}
head(z)

for (x in 999:100){
                  temp <- x*z
                  product <- c(product, temp)}
head(product)

# Since we are looking for a six digit Palindrome, we can remove those elements
# which are smaller
product <- product[product >= 100001]
tail(product)

# Sorting in descending order will make the search for the largest Palindrome
# easier
product <- sort(product, decreasing=T)

# Here match is working somewhat similar to the vlookup of Excel.
# It will provide the position of element of the list of Palindrome for which
# there is a match in the list of all prodcuts.
palindromes <- match(palin, product)

# We remove the NAs which were prodcuded for matches
palindromes <- na.omit(palindromes)

# This is the postion which will hold the largest Palindrome in the product list
palindromes[1]

# This is the largest Palindrome
product[368]


################################################################################

# Problem 5

# 2520 is the smallest number that can be divided by each of the numbers
# from 1 to 10 without any remainder. What is the smallest positive
# number that is evenly divisible by all of the numbers from 1 to 20?

# Did this manually. Need some code to explain.


################################################################################

# Problem 6

# The sum of the squares of the first ten natural numbers is,
# 1^2 + 2^2 + ... + 10^2 = 385
# The square of the sum of the first ten natural numbers is,
# (1 + 2 + ... + 10)^2 = 55^2 = 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.


# Approach 1 - The R approach
x.1 <- (1:100)
y.1 <- x.1^2
head(y.1)
a.1 <- sum(y.1)
b.1 <- (sum(x.1))^2
b.1 - a.1
b.1


################################################################################


# Problem 7

# By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
# What is the 10,001st prime number?


# We can use the Sieve of Eratosthenes algorithm
x <- c(1:10^6)
y <- 1

library(schoolmath)
for (i in 1:length(x)){
                      if (is.prim(x[i])) {y[i] <- i}}

primes <- na.omit(y)
primes <- primes[-1]
head(primes)
primes[10001]


x.2 <- c(2:10^6)
y.2 <- 2
i <- c(2:sqrt(length(x.2)))
non.primes <- 1

for (y.2 in 2:sqrt(length(x.2))){
                             temp <- y.2*i
                             non.primes <- c(non.primes, temp)}

non.primes <- unique(sort(non.primes))

check.prime <- x.2 %in% non.primes

prime.index <- 0

m <- 0

for (j in 1:length(check.prime)){
                               if (check.prime[j] == "TRUE") {prime.index[j] <- 0}
                                else {m <- m + 1
                                  prime.index[j] <- m}}


################################################################################


# Problem 8

# Find the greatest product of five consecutive digits in the 1000-digit number.
#                     73167176531330624919225119674426574742355349194934
#                     96983520312774506326239578318016984801869478851843
#                     85861560789112949495459501737958331952853208805511
#                     12540698747158523863050715693290963295227443043557
#                     66896648950445244523161731856403098711121722383113
#                     62229893423380308135336276614282806444486645238749
#                     30358907296290491560440772390713810515859307960866
#                     70172427121883998797908792274921901699720888093776
#                     65727333001053367881220235421809751254540594752243
#                     52584907711670556013604839586446706324415722155397
#                     53697817977846174064955149290862569321978468622482
#                     83972241375657056057490261407972968652414535100474
#                     82166370484403199890008895243450658541227588666881
#                     16427171479924442928230863465674813919123162824586
#                     17866458359124566529476545682848912883142607690042
#                     24219022671055626321111109370544217506941658960408
#                     07198403850962455444362981230987879927244284909188
#                     84580156166097919133875499200524063689912560717606
#                     05886116467109405077541002256983155200055935729725
#                     71636269561882670428252483600823257530420752963450


# This is an easy one. Just take the number and paste in any text editor. Next, make each digit
# take one row and hence you will get a file with 1000 rows of data.

# Read the text file in R.
x <- read.table("big_number.txt")

# We can use a for loop as well, but that won't show the beauty, elegance and power of R.
# Just install and call the library "zoo". "zoo" here has no connection to the man-made
# constrained habitat for animals, like the one in Madagascar. It was created by Achim Zeileis and
# stands for Zeileis' Ordered Observations and is popular package for dealing with Time Series data.
library(zoo)
x <- zoo(x)
# why we do this will be clear below.

# "rollapply" is a function in the "zoo" package that performs a repeated task dictated by a funtion
# a rolling window of fixed length.
# Here we are asking "rollapply" to take 5 digits at a time, or rather 5 rows at a time, from the zoo object
# x and find the product of 5 rows.
# "rollapply" only takes zoo objects as the input data and hence we have converted x to a zoo object above.
products <- rollapply(x, 5, FUN=prod)
head(products)

max(products)
# This gives the maximum product among the 1000 prodcuts that "rollapply" has found.


################################################################################


# Problem 9

# A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,
# a^2 + b^2 = c^2
# For example, 3^2 + 4^2 = 9 + 16 = 25 = 5^2.
# There exists exactly one Pythagorean triplet for which a + b + c = 1000.
# Find the product abc.

# Approach 2
system.time(for(a in 1:500){
                        for(b in (a+1):500){
                                c <- 1000 - (a + b); if(a*a + b*b == c*c) print(c(a, b, c))}})


#################################################################################


# Problem

# Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.

y <- readLines("150digit.txt")
y <- as.numeric(y)
sum(y)
sub <- substring(y, 1, 1)

for (i in 2:50){
                temp <- substring(y, i, i)
                sub <- c(sub, temp)}

sub <- as.numeric(sub)
is.numeric(sub)
length(sub)
count <- 0
sum(sub)
for (j in 1:9){
              count[i] <- sum(sub[sub == j])}


####################################################################################


# Problem 10

# The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
# Find the sum of all the primes below two million.

# Approach 1

a <- 0
library(gmp)
system.time(for(i in 2:2000000){
              if (length(factorize(i)) == 1){a[i] <- i} else {a[i] <- 0}})
sum(a[a != 0])


####################################################################################


# Problem 11
# In the 20*20 grid below, four numbers along a diagonal line have been marked in red.

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

# The product of these numbers is 26  63  78  14 = 1788696.

# What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 2020 grid?

# Rolling window of 4*4 matrices selecting the maxmimu product from each window.
big.grid <- read.delim("20grid.txt", header = F, sep = " ")

max.product <- function(my.data, p){
                      my.data <- as.data.frame(my.data)
              # max.small.products <- rep(NA, ((ncol(big.grid) - p + 1)*(nrow(big.grid) - p + 1))
                max.small.products <- 0
                    for(i in 1:(nrow(my.data) - p + 1)){
                          for (j in 1:(ncol(my.data) - p + 1)){
                            small.grid <- data.frame(c(my.data[i:(i + (p - 1)), j:(j + (p - 1))]))
                                for(m in 1:p){
                                    max.small.products <- rbind(max.small.products, max(prod(small.grid[m,]),
                                                        prod(small.grid[,m]), prod(diag(as.matrix(small.grid))), prod(diag(as.matrix(rev(as.data.frame(small.grid)))))))}}}
                              return(max(max.small.products[,1]))}

max.product(big.grid, 4)


####################################################################################


# Problem 12

# The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

# 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

# Let us list the factors of the first seven triangle numbers:

# 1: 1
# 3: 1,3
# 6: 1,2,3,6
# 10: 1,2,5,10
# 15: 1,3,5,15
# 21: 1,3,7,21
# 28: 1,2,4,7,14,28

# We can see that 28 is the first triangle number to have over five divisors.

# What is the value of the first triangle number to have over five hundred divisors?

# Approach 1:

# Use the divisors package. :)
library(divisors)


tri.div <- function(num.div){
                           for(n in 1:10000000){
                                    x <- n*(n + 1)/2
                            if (numdivs(x) > num.div) {return(x)}
                                }}

####################################################################################


# Problem 13

# If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.

# {20,48,52}, {24,45,51}, {30,40,50}

# For which value of p<=1000, is the number of solutions maximised?

a <- NA
b <- NA
c <- NA
data <- data.frame(a, b, c)

PyTriples <- function(p, dataset){
  count <- 1
  for(c in floor(p/3):floor(p/2)){
    for(b in floor(p/4):floor(p/2)){
      for(a in 1:floor(p/3)) {
        if (a^2 + b^2 == c^2 & c > b & b > a ) {dataset[count,] <-  c(a, b, c); count <- count + 1}
        }}}
  return(dataset)}

system.time(data <- PyTriples(1000, data))

data$sum <- data[, 1] + data[,2] + data[,3]

data.new <- data[data$sum <= 1000,]

aggregate(data.new, by = list(data.new$sum), FUN = length)


####################################################################################

# Problem 14

# The following iterative sequence is defined for the set of positive integers:

# n -> n/2 (n is even)
# n -> 3n + 1 (n is odd)

# Using the rule above and starting with 13, we generate the following sequence:

# 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
# It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

# Which starting number, under one million, produces the longest chain?

# NOTE: Once the chain starts the terms are allowed to go above one million.


Collatz <- function(limit){
  prev <- rep(-1, limit)
  prev[1] <- 0

  for(i in 2:limit){
    m <- i
    step <- 1
    while (m >= i) {
      step <- step + 1
    if(m %% 2 == 0) m <- m/2
    else m <- 3*m + 1
    }
  prev[i] <- prev[m] + step
  }
  return(prev)
}
system.time(Collatz.num <- Collatz(1000000))
which(Collatz.num == max(Collatz.num))

####################################################################################


# Problem 16

# 2^15 = 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^1000?

library(gmp)
# library(Brobdingnag)

x <- as.bigz(2^1000)

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

####################################################################################

# Problem 19

# You are given the following information, but you may prefer to do some research for yourself.

# 1 Jan 1900 was a Monday.
# Thirty days has September,
# April, June and November.
# All the rest have thirty-one,
# Saving February alone,
# Which has twenty-eight, rain or shine.
# And on leap years, twenty-nine.

# A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.
# How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?


l <- as.Date("1901-01-01", format = "%Y-%m-%d")
as.numeric(l)
u <- as.Date("2000-12-31", format = "%Y-%m-%d")

day <- rep(NA, u-l)
date <- rep(NA, u-l)

dates <- data.frame(day, date)

count <- 1

system.time(for(i in l:u){
  dates[count, 1] <- weekdays(as.Date(i, origin = "1970-01-01"))
  dates[count, 2] <- i
  count <- count + 1
})

dates[, 2] <- as.Date(dates[,2], origin = "1970-01-01")

dates$my.date <- substr(dates$date, 9, 10)

dates <- dates[dates$my.date == "01", ]

aggregate(dates, by = list(dates$day), length)

table(dates1$day)

####################################################################################

# Problem 20

# n! means n  (n  1)  ...  3  2  1

# For example, 10! = 10  9  ...  3  2  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!

library(gmp)

x <- factorialZ(100)

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

####################################################################################


# Problem 48

# The series, 11 + 22 + 33 + ... + 1010 = 10405071317.

# Find the last ten digits of the series, 11 + 22 + 33 + ... + 10001000.

x <- as.bigz(999^99)
y <- as.brob(999^999)
y
for(i in 1:100){x <- as.bigz(x) + as.bigz(i^i)}
x


####################################################################################


# Problem 18

# By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

# 3
# 7 4
# 2 4 6
# 8 5 9 3

# That is, 3 + 7 + 4 + 9 = 23.

# Find the maximum total from top to bottom of the triangle below:

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

# NOTE: As there are only 16384 routes, it is possible to solve this problem
# by trying every route. However, Problem 67, is the same challenge with a triangle
# containing one-hundred rows; it cannot be solved by brute force, and requires a
# clever method! ;o)

tri <- read.csv("problem18.csv", header=F)

system.time(for(row in nrow(tri):1){
 for(col in 1:row){
  tri[row-1, col] = tri[row-1,col] + max(tri[row, col], tri[row,col + 1])
 }
})
tri[1,1]


####################################################################################


# Problem 67

# By starting at the top of the triangle below and moving to adjacent numbers on
# the row below, the maximum total from top to bottom is 23.
#
# 3
# 7 4
# 2 4 6
# 8 5 9 3
#
# That is, 3 + 7 + 4 + 9 = 23.
#
# Find the maximum total from top to bottom in triangle.txt
# (right click and 'Save Link/Target As...'), a 15K text file containing a triangle
# with one-hundred rows.
#
# NOTE: This is a much more difficult version of Problem 18.
# It is not possible to try every route to solve this problem, as there are 299 altogether!
#  If you could check one trillion (1012) routes every second it would take over
# twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)

tri <- read.csv("problem67.csv", header=F)

system.time(for(row in nrow(tri):1){
 for(col in 1:row){
  tri[row-1, col] = tri[row-1,col] + max(tri[row, col], tri[row,col + 1])
 }
})
tri[1,1]


####################################################################################


# Problem 81

# In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by only moving to the right and down, is indicated in bold red and is equal to 2427.
#
#
# 131 673	234	103	18
# 201	96	342	965	150
# 630	803	746	422	111
# 537	699	497	121	956
# 805	732	524	37	331
#
# Find the minimal path sum, in matrix.txt (right click and 'Save Link/Target As...'),
# a 31K text file containing a 80 by 80 matrix, from the top left to the
# bottom right by only moving right and down.


# Manhattan Tourist Problem
mat <- read.csv("problem81.csv", header=FALSE)

for(row in 2:nrow(mat)){
 mat[row, 1] <- mat[row-1,1] + mat[row, 1]
}

for(col in 2:ncol(mat)){
 mat[1, col] <- mat[1,col-1] + mat[1, col]
}

for(row in 2:nrow(mat)){
 for(col in 2:ncol(mat)){
  mat[row, col] <- min(mat[row-1,col] + mat[row, col], mat[row, col-1] + mat[row,col])
 }
}
mat[nrow(mat),ncol(mat)]

####################################################################################

# Problem 17

# If the numbers 1 to 5 are written out in words: one, two, three, four, five,
# then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.

# If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words,
# how many letters would be used?

# NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains
# 23 letters and 115
# (one hundred and fifteen) contains 20 letters. The use of "and" when writing out
# numbers is in compliance with British usage.


####################################################################################

# Problem 15

# Starting in the top left corner of a 2x2 grid, there are 6 routes (without backtracking) to the bottom right corner.

# How many routes are there through a 20x20 grid?

grid <- 200

mat <- matrix(NA, nrow = grid + 1, ncol = grid + 1)
mat[,1] <- rep(1, grid + 1)
mat[1,] <- rep(1, grid + 1)

system.time(
  for(row in 2:nrow(mat)){
  for(col in 2:ncol(mat)){
    mat[row, col] <- mat[row-1,col] + mat[row, col-1]
  }
}
)
mat[nrow(mat),ncol(mat)]
No results found