My Blog

Euler Problem 36 – Double-base palindromes

Double-base palindromes

Problem 36

The decimal number, 585 = 10010010012 (binary), is palindromic in both bases.

Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.

(Please note that the palindromic number, in either base, may not include leading zeros.)

This looks a straight forward problem where I have used the brute force method to solve the problem. We need to find numbers which are palindrome in base 10 as well as base 2. There is a function intToBin from R.Utils package which gives a base 2 number. To check if a number is a palindrome or not we can just reverse the number and see if it same as the original number. We can reverse a number using the traditional method (dividing by 10 and keep the remainder) but we have a direct function stri_reverse in stringi package which reverses the number.

So for each number we check if base 10 number is palindrome as well as base 2 representation of that number is palindrome as well. If they satisfy both the condition then we add them in the double_base palindrome list. Also, at first I was checking both the conditions in one line itself with an “and” (&) operator but when I separated the two conditions I could see a huge performance improvement because we are not evaluating both the conditions now. For every number we evaluate the second condition only for those numbers which pass the first condition hence the improvement.

library(R.utils)
library(stringi)

get_double_base_palindrome_under_n = function(n) {
   numvec = numeric()
   for(i in seq(n)) {
     if(i == stri_reverse(i))
       if(intToBin(i) == stri_reverse(intToBin(i)))
          numvec = c(numvec, i)
 }
return(sum(numvec))
}

get_double_base_palindrome_under_n(1000000)
#[1] 872187

#With combined-if condition
System.time(get_double_base_palindrome_under_n(1000000))
#user      system     elapsed
#188.676   1.066      191.634

#With separate-if condition
System.time(get_double_base_palindrome_under_n(1000000))
#user  system elapsed
#3.485   0.014   3.513

 

Advertisements

Euler Problem 35 – Circular Primes

Circular primes

Problem 35

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?

The approach which I thought of was to find all the prime numbers below million, apply circular shift on them, check if those are prime as well and then include them in the list of circular primes.

I had thought I had already written a function to get all the prime numbers under n before. After going through all the previous codes I could not find it anywhere so decided to write one myself. At first I thought of using the is_prime function from Problem 3 for every odd number but this was very much time consuming for million numbers. Then after searching extensively for fastest way to get prime numbers under n I got directed to Sieve of Eratosthenes.

The concept for Sieve of Eratosthenes is you have an array of numbers from 1 to n. 2 is a prime number and then remove all the numbers which are multiples of 2 under n. Then take next number which is 3, 3 is prime and remove all the numbers which are multiple of 3. Now, 4 is already cancelled from the previous instance of 2. We move to 5, 5 is prime and remove all the multiples of 5 under n and we continue this till we reach end of the list. So you basically take the current first element in the list, add it in the prime number list and remove its multiples from the list. No need to do any additional check if it is prime or not because if the number is not prime it would definitely be a multiple of some other number from the past numbers which we have already encountered and would cancel it out.

get_primes_under_n = function (n) {      
  num_seq = seq(3, n, 2) 
  prime_number = numeric()     
  while(length(num_seq) >= 1) {
      prime_number = c(prime_number, num_seq[1])
      num_seq = setdiff(num_seq, seq(num_seq[1], n, num_seq[1]))
   }
   return(c(2, prime_number))
  }

I wrote this function for Sieve of Eratosthenes which takes up most of the computing time in the function. Moving forward, we now have all the prime numbers under n, now for each prime we need to check if its circular rotations are prime as well. At first, I was confused here. I thought we have to check for each possible combination of those numbers. So for eg : For 123, we need to check for 123, 231, 312, 132, 213 and 321 which wasn’t true. We just need to check for circular rotations which includes 123, 231 and 312.

Unfortunately, in R we do not have a function as of now which will do this circular shifting directly. (Although, I think it is proposed in next release of data.table somewhere). Anyway, Jaap from SO helped me to write a function which does this circular shift which I later modified a little according to my requirement.

cyc_shift = function(x) {
    if(length(x) == 1) return(x)
    comb = paste0(x, collapse = "")
    n <- nchar(comb) - 1 
    c(comb, lapply(1:n, function(i) paste0(c(tail(x,-i),  
  head(x,i)), collapse = "")))
} 

This basically takes a character array and circular shifts it and sends the output. So basically consider this –

split_num 
#[1] "1" "2" "1" "3" 

cyc_shift(split_num)
#[[1]]
#[1] "1213"

#[[2]]
#[1] "2131"

#[[3]]
#[1] "1312"

#[[4]]
#[1] "3121"

Before sending the prime number to circular shift function we check if it contains any of the even number c(0, 2, 4, 6, 8) because if it does then it cannot be circular prime as when we circular shift the numbers that number would atleast be once in the units place which would make it divisible by 2 and eventually it would be rejected. After the number has passed this test, we pass it to cyc_shift function to get all the circular shifted arrays and we check if they all are prime as well. As we had precalulated the prime numbers under n already we can check if all these circular shifted numbers are present in that array.

count_circular_primes = function(num) { 
     prime_numbers = get_primes_under_n(num) 
     final_answer = numeric() 
     for(i in prime_numbers) { 
         split_num = strsplit(as.character(i), "")[[1]] 
#If it contains any of the even digit then it is going to be divisible by 2 in #any one of the circular shift operation 
         if (any(split_num %in% c("0","2","4","6","8")) & length(split_num) > 1) 
               next

     all_nums = as.numeric(cyc_shift(split_num))
#All possible variations should be prime numbers, hence should be included in #the prime numbers we had calculated previously
     if (all(all_nums %in% prime_numbers))
       final_answer = c(final_answer, i)
   }
   return(length(final_answer))
}

You can see the entire code on Github.

Euler Problem 34 – Digit Factorials

Digit factorials

Problem 34

145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.

Find the sum of all numbers which are equal to the sum of the factorial of their digits.

Note: as 1! = 1 and 2! = 2 are not sums they are not included.

I have skipped problem 33 as of now because I didn’t feel like solving it actually. This was fairly simple problem to understand and it was simple to program as well. This was more or less like Problem 30 where the only thing you have to do is find the upper bound till what limit you have to check the factorials. Here if you see digits can take range of 0-9, so 9! X 7 = 2540160 which is a 7 digit number. Also 9! X 8 is 2903040 which is also a 7 digit number. So our upper limit is 2540160 as any 8 digit number can’t go beyond 2903040.

We first need to separate a number into different digits, calculate their factorial and take sum of it. So to avoid unnecessary calculating the factorial again and again I create a list of 10 numbers consisting of factorial from 0-9 and after we split the number into separate digits we can get the respective factorial value from the list, sum them all together and check if it is same as the number. If it is then add it to the list and go to the next number.

This is a donkey method which I have approached this time. Maybe because last question took lot of time and I needed to complete this asap. I think there might be certain ways in which we can reduce certain iterations.

 
get_digit_factorials <- function() {
   numx <- seq(0,9)
   factorial_list = factorial(numx)
   names(factorial_list) <- numx
   numvec <- numeric()
   for(i in seq(3, 2540160)) {
      split_chars = strsplit(as.character(i), "")[[1]]
         if(sum(factorial_list[split_chars]) == i)
            numvec = c(numvec, i)
    }
    return(sum(numvec))
  }

get_digit_factorials()
#[1] 40730

system.time(get_digit_factorials())
#user  system elapsed
#9.420   0.091   9.607

 

Euler Problem 32- Pandigital Products

Pandigital products
Problem 32
We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.
The product 7254 is unusual, as the identity, 39 × 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.
Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.
HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.

I know I have been away for a very long time but what can I do, my script was running all this time to get the answer for this question. 😛 Ok, jokes apart not all this time but for many days 😦 . First of all I was trying to find a solution myself. We could use a donkey method approach to solve this but I was completely against it. (In other news, I found out that the donkey approach is called as brute force method 😛 ). I had one logic, in mind which was not a donkey approach and seemed correct.

My idea was, we generate all possible combinations of 9 digit numbers from 1-9, (876543219 and so on) then we split them into different combinations of multiplicand (say 876) and multiplier (say 219) and see if their product was equal to the remaining part(543) of the number. I thought this could be possible as we are checking only 9 digit numbers and it would save up so many unnecessary computation. However, I could not code it up properly and I decided to move on with the donkey approach.

After wasting good amount of time on non-donkey approach and reaching nowhere I decided to follow the donkey approach. The donkey approach was simple. Multiply every number with every other number and check if the combination of multiplicand, multiplier and dividend make up pandigital number. If it does then save the number else just go to the next number. Now one thing to decide was to decide the threshold, we can’t keep on multiplying all the numbers with all the numbers. There has to be some threshold till where we would multiply because numbers have no end. So to decide a threshold I selected a number which I was 100% sure. I selected a million (1, 000, 000) to be the threshold. I think this was way too safe but I purposefully selected this big number as I didn’t wanted to miss out on any possible scenario which if we need to debug later is quite difficult. Now we multiply these two numbers and paste them together with their product. After this we need to check if these combination of numbers make a pandigital number.

I wrote a separate function to check if a number is a pandigital number or not. It checks if all the numbers from 1-9 are present in the number and also they should occur only once.

is_pandigital <- function(number) {
number_digits <- as.numeric(strsplit(as.character(number), "")[[1]])
return (all(1:9 %in% number_digits) & all(table(number_digits) == 1))
}

If this returns true then we save the number as pandigital number and if it is false then we continue with the loop.

So far so good. Looks very simple, right? Yeah, that is the advantage of donkey approach it is very simple. As far as this program is concerned it is fine until you execute it. Once I ran this program, I waited for 10 mins, 20 mins, 30 mins, an hour and even 2 hours but still the program was running. I thought there might be some issue in my code or it might be running in an infinite loop but I couldn’t find any such catch. I then printed the numbers in the loop so that I know what is the current status of the calculation, turns out it was correct, it takes this amount of time to process. This time it was more than 3 hours and it was still running, I couldn’t complete it on my local system so I had a server where I ran my code. I optimized where a little where I could find scope. For example, instead of sending every number to is_pandigital function I send only those numbers which have 9 digits in them but still it was not going to drastically improve the run time. Looking at the output from the print statement I immediately figured that the R server was slower than my local machine. Anyway, I was at least not worried now to check again and again when the run would be completed and I could do other tasks on my system.

At the end of the day, I just checked on the status of the computation and it had a long way to go. I realized that this is not a simple process and it is going to take lot of time to complete this. I was just wishing that it gives me the correct output at the end of the complete run cycle. I cannot afford getting a wrong answer after waiting for so long. Fortunately, enough when I checked my answer, it was correct and I finally could relax.

 

is_pandigital <- function(number) {
  number_digits <- as.numeric(strsplit(as.character(number), "")[[1]])
  return (all(1:9 %in% number_digits) &  all(table(number_digits) == 1))
}

numvec = numeric()
for (i in seq(100000)) {
  for (j in seq(i, 100000)) {
    combined_number = paste0(i, j, i*j)
    print(c(i, j))
    if (nchar(combined_number) == 9) {
      if (is_pandigital(combined_number))
      {
        numvec = c(numvec, i*j)      
      }
    }
  }
}

sum(unique(numvec))
#[1] 45228

Download YouTube videos using the YouTube Data API

Sometimes I get bored of watching my favorite show. So at that time I start surfing YoutTube. I am a big YoutTube fan. When I am at home and not sleeping 90% of the time in one of my tab YoutTube would be open. Maybe listening to songs or watching some random video. I prefer downloading the video and then watch it on TV which has a better screen and better resolution. If there is just an episode or two which I want to see, then I can download it from many web sources. Usually there are lot of web series on YoutTube which I am interested to watch which has got various episodes. Now it is quite boring to download all those episodes one by one so I thought of writing a script which could do exactly the same.

I am using the pafy library for YouTube in python which allows to download the videos along with many other things as well. We access the YoutTube data API, to get all the data. So to start we need to first get YoutTube keys as explained in this tutorial. Once we authorize the application , we can make different calls to the YouTube API. If you observe any video on YouTube it starts with https://www.youtube.com/watch?v=, the part which follows this is the unique alphanumeric string which decides the video to play. Now the task is to find that unique string and send it to download_videos function which adds the above prefix and creates a unique string for all the videos and downloads the best quality videos.

def download_videos(url_lists) :

    prefix = "https://www.youtube.com/watch?v="
    updated_url_lists = [prefix + s for s in url_lists]
    for url in updated_url_lists:
        video = pafy.new(url)
    best = video.getbest(preftype="mp4")
    filename = best.download(quiet=False)

Now how do we get those unique strings ? There are two functions which I have written to get those parts. One is by keyword search. So it works same as when you search for a keyword in Youtube  and it returns you the result. It would return the same list depending on the maxResults number which you have sent as parameter. The response object has got an items object which has all the details of the result in it. We get those unique strings by extracting the videoId variable in each list.

def youtube_search_by_term(service, keyword):
     search_response = service.search().list(
                       q=keyword, part="id",
                       maxResults=20).execute()
     url_lists = []
     for item in search_response['items'] :
         try:
            url_lists.append(item['id']['videoId'])
         except :
            pass
return url_lists

We can also download all the videos from a particular playlist.

def channels_list_by_channel_playlist(service):

get_playlist_items = service.playlistItems().list(
                    part='snippet,contentDetails',
                    maxResults=10,playlistId='your_playlist_ID').execute()

url_lists = []
for items in get_playlist_items['items'] :
    url_lists.append(items['snippet']['resourceId']['videoId'])

return  url_lists

Select random files including subfolders

I am trying to include some stuff which I use for my day-to-day activities. This is a short blog about selecting random files from a folder. I have downloaded various seasons of my favorite series of all time in my laptop. Each season has a different folder and every season has many episodes in it. I usually select random episodes manually, transfer it to USB and watch them on TV. Slowly slowly I found out that there was so much of bias in me selecting those episodes. I was ending up selecting the same episodes every time and although how much interesting/funny the episodes are we get bored if we keep on seeing the same ones again and again.

So to avoid this biasness I decided to write a script which randomly selects n files and transfers it to your prescribed directory.

get_random_files <- function(n) {

#list.files lists all the files in the directory and sample selects n random entries in it
files = sample(list.files("outermost_directory_path", recursive = TRUE), n)

#filter only those files which are required, here ending with mkv
filename = paste0("complete_directory_path_name", files[grepl("mkv$", files)])

#copy the files to your desired directory
file.copy(filename, to = "your_directory_path")
}

list.files lists all the files in the directory mentioned whereas sample selects n random files from it. The parameter recursive = TRUE ensures that it also lists the files in the subdirectories (if any) as well. list.files only gives the name of the file to get the complete relative path we append it with paste0 the directory name to get the correct path. (I later realized that there is full.names parameter which will give what we want directly and we can skip the second step completely). Sometimes if we have certain other files which we want to ignore, we can filter them according to our requirement. I have done that using grepl where only files with extension “mkv” would be selected. The third command just copies the files from path to destined path.

Euler Problem 31 – Coin Sums

Coin sums

Problem 31

In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

It is possible to make £2 in the following way:

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

How many different ways can £2 be made using any number of coins?

This was a real difficult one, it was beyond my reach. I didn’t know how could I program this. For once, I sat down with pen and paper to solve it but there were so many possible combinations of forming the solution that I was numb and couldn’t think of anything.

After a few unsuccessful attempts of trying to find a general solution for the problem, I stumbled upon Dynamic programming. I have heard and read about it but have never used it.  Wikipedia defines dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions.” . Does it sound familiar ? Yes, it did for me as well. Isn’t this same as recursion ? Well, at first I thought the same but there is one slight difference which is in the last part of the definition which says “storing their solutions.” . So in dynamic programming we just calculate the subproblem once and store the solution if we need the same calculation again we just take the already stored values unlike recursion where we would re-calculate the subproblem again. So dynamic programming is a sub problem of recursion, I think ?

I also came across this excellent blog which gives two excellent approaches to solve the problem. I haven’t done much in this problem, just converted the C# solution in the blog to R. I am not explaining the approach since there is nothing new in my approach it is same as in the blog. The only difference is in second approach where to just save one iteration I have initialized the array with 1 , since any target sum with denomination of only 1 would have only one way to reach to the target. Also I am expecting the coins array to be without 1 as denomination as we have already considered that case.

get_coin_sums = function(target) {
  ways = 0
  for (a in seq(target, 0, -200)){
    for (b in seq(a, 0, -100)) {
      for (c in seq(b, 0, -50)) {
        for (d in seq(c, 0, -20)) {
          for (e in seq(d, 0, -10)) {
            for (f in seq(e, 0, -5)) {
              for (g in seq(f, 0, -2)) {
                ways = ways + 1
              }
            }
          }
        }
      }
    }
  }
  return(ways)
}

get_coin_sums(200)
#[1] 73682
system.time(get_coin_sums(200))
#user  system elapsed 
#0.046   0.001   0.047 

Both the approaches are efficient but the second approach is super fast and completes in very less time.

get_coin_sums_dynamic = function(target, coins) {
#coins should be an array without inclusion of 1
#initialize all the values to 1
  summation = rep(1, target + 1)
  for(i in coins) {
    for(j in seq(i, target)) {
      summation[j + 1] = summation[j + 1] + summation[j - i + 1]
    }
  }
  return(tail(summation, 1))
}

get_coin_sums_dynamic(20, c(2, 5, 10))
#[1] 40

get_coin_sums_dynamic(200, c(2, 5, 10, 20, 50, 100, 200))
#[1] 73682
system.time(get_coin_sums_dynamic(200, c(2, 5, 10, 20, 50, 100, 200)))
#user  system elapsed 
#0       0       0 

Euler Problem 30 – Digit fifth powers

Digit fifth powers

Problem 30

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

1634 = 14 + 64 + 34 + 44
8208 = 84 + 24 + 04 + 84
9474 = 94 + 44 + 74 + 44

As 1 = 14 is not a sum it is not included.

The sum of these numbers is 1634 + 8208 + 9474 = 19316.

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

Pretty disappointed at this problem. This is my 30th problem and with each problem project Euler were raising their bar and this did brought it down. Anyway, one cannot be awesome all the time. There are going to be ups and down and I accept that and move ahead expecting more amazing questions from them ahead.

After reading the problem, as usual the donkey approach came to my mind. Start from number 1 to some threshold number, calculate for each number sum of its fifth exponent and check sum of which number is equal to that number. I usually try to avoid such donkey approach and here I thought there might be some trick to find the solution, I was not sure what though.

I wrote all the 4th and 5th power of numbers 1-9 on paper, found out the differences between them. Is there a way we could deduce the answer from the 3 numbers given in the question itself. There might be some connection. Also noticed that the sum of numbers for fourth power were 1634 – 14, 8208 – 18, 9474 – 24. I don’t know why I did that but was just trying to find out various ways in which I could find out some trick / pattern which will take me to the answer. Invested so much of my time, my brain was exploding thinking of what can it be. Thought pf giving up 3-4 times and just google the answer but I waited, waited for some more time. Scratched my head, scratched my pillow, scratched my bedsheet but nothing seems to be clicking and then I just thought I’ve had it. I am going to look for the solution , I am done.

I was just going to search for the answer but then I thought that anyway, I am not getting the answer lets use the donkey approach and see if we get the answer. At least we would have a satisfaction that we reached to the answer ourselves without any help. So now, how to decide the upper limit? Okay I just guessed, 9999 and it gave me two numbers which satisfies the condition. Increased the limit to 999999 and I got 4 more numbers then increased the limit further to 99999999 and there were no new numbers but the loop just took more time. So 999999 it is. Summed all the numbers and checked the answer and booomm, it was right!!

sum_to_fifth_power = function() {
   all_numbers = numeric()
   for(i in seq(2, 999999)) {
      individual_raised_to_5 = as.numeric(strsplit(as.character(i), "")[[1]])^5
      if(i == sum(individual_raised_to_5)) {
         all_numbers = c(all_numbers, i)
      }
     }
   return(sum(all_numbers))
}

sum_to_fifth_power()
#[1] 443839

system.time(sum_to_fifth_power())
#user  system elapsed
#9.53    0.00    9.57

So, not bad for a problem where the only thing which I did was guessing. I quickly googled up to find the trick which I was missing and not able to get it and you know what? There is no trick to find this. I checked so many sources and all of them following the same approach. The only trick which is present is how to find the upper limit. They had some logic in there which said that we only need to find numbers up to this number and not others which I didn’t get. Anyway, I wasn’t even interested in that because that thing I just ended up with pure guessing and it worked. However, it was depressing to see there was no intelligent solution to this and it was only donkey approach which we needed to follow. Sigh!!

BTW, if you are interested these are the numbers which satisfied the condition :

4150   4151  54748  92727  93084 194979

Euler Problem 29 – Distinct Powers

Distinct powers

Problem 29

Consider all integer combinations of ab for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:

22=4, 23=8, 24=16, 25=32
32=9, 33=27, 34=81, 35=243
42=16, 43=64, 44=256, 45=1024
52=25, 53=125, 54=625, 55=3125

If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

How many distinct terms are in the sequence generated by ab for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?

This one was easy to understand so it did not take much of my time unlike last problem. The first and the donkey approach which comes to mind is to calculate values for each combination of a = 2 to 100 and b = 2 to 100 and then select only the unique combinations and the length of it is the answer. Simple, right? The only difficult part would be to use some special libraries (like gmp etc.) to handle these large numbers because the maximum number which we would encounter in this problem is 100100 and it would be a very big number and again the precision would come into picture.

However, I wasn’t interested in this donkey approach. Whenever there is a scope to follow a non-donkey approach I would definitely prefer that approach and here there was a clear scope. We know overall there are going to be 99 (2-100) X 99 (2-100) elements. Now out of this we need to find out which are the ones that are overlapping and repeating. If we could find that then we can just subtract those numbers from 99 X 99 and that would be the answer. In what way can we know that 24 and 42 have the same value without evaluating their respective values?

If 24 = 42, does that mean every x = y but that was proved wrong immediately with 25 != 52 and many such examples. Thought about various approaches when suddenly I thought of this one. What does it mean when we say xy ? It means x is multiplied to itself y times. For example : 24 = 2 X 2 X 2 X 2.

Similarly when it is 42 we split 4 into 2 X 2 and then repeat it 2 times to get 2 X 2 X 2 X 2 and now both these numbers are equal. So what we can do is split each into its prime factors and repeat it for b times. Do this for each combination of a and b and then select only the unique values. I was trying to use the getfactors function in some way but our requirement is a bit different here. So I ended up writing my own get_prime_factors function.

 
get_prime_factors = function(n) {
   numvec = numeric()
   while(n %% 2 == 0){
     numvec = c(numvec, 2)
     n = n/2
   }
   i = 3
   while(n != 1) {
     while(n %% i == 0) {
       numvec = c(numvec, i)
       n = n/i
     }
    i = i + 2
  }
   return(sort(numvec))
}

So this gives all the prime factors as output. Some examples :

get_prime_factors(100)
[1] 2 2 5 5

get_prime_factors(164)
[1]  2  2 41

get_prime_factors(81)
[1] 3 3 3 3

For each a we get its factors as product of prime factors and repeat these prime factors b times and maintain a list for each combination and then count the unique ones.

source("C:/Users/Ronak Shah/Google Drive/Git-Project-Euler/29. Get_Prime_Factors.R")

source("C:/Users/Ronak Shah/Google Drive/Git-Project-Euler/29. Get_Prime_Factors.R")
get_distinct_powers_in_range <- function(min_range, max_range) {
  all_list = list()
  i = 0
  range = seq(min_range, max_range)
  for(a in range) {
    prime_factors = get_prime_factors(a)
    for(b in range) {
      i = i + 1
      all_list[[i]] = rep(prime_factors, each = b)
    }
  }
  return(length(unique(all_list)))
}
get_distinct_powers_in_range(2, 100)
#[1] 9183

system.time(get_distinct_powers_in_range(2, 100))
#user  system elapsed 
#0.41    0.00    0.40

Okay, efficiency wise I am not sure if this is any efficient than the donkey approach because even here we are taking into account all the possible combinations of a and b, and I don’t see a possible shortcut. However, the good point is we are finding the correct answer even without evaluating the number and its power. So no need to worry for handling large numbers and precision.

After I submitted the answer, I googled the question to know if somebody has used a better/different/easy approach than this. However, the first 3-4 links which I opened, all were following the donkey approach and nobody had mentioned this approach so I am kind of proud of myself. 😀

Euler Problem 28 – Number Spiral Diagonals

Number spiral diagonals

Problem 28

Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:

21 22 23 24 25
20  7  8  9 10
19  6  1  2 11
18  5  4  3 12
17 16 15 14 13

It can be verified that the sum of the numbers on the diagonals is 101.

What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way?

I had to read this question for 10-15 times to get a little of what it means. At first, I was so sure that I will not able to solve this. It was so weird, so complicated. I was not able to understand how this matrix was formed. I was assuming it started at position [1, 1] with value 1 and moved cell by cell to right and it is now into its current state and we need to do the same with the 1001 X 1001 matrix. Although, with this logic it was understood that 1 can reach till its position but how did 2, 3 reach their respective positions. The logic wasn’t clear and I was highly doubtful if I was even thinking in the right direction.

It was after a lot of thinking and few unsuccessful attempts I realized that the name suggests the matrix is formed in a spiral way. If you follow the numbers you’ll understand that it is a spiral increasing slowly as dimensions of the square increases. It was too dumb of me to take so much of time to find this pattern out. I have experienced it so many times that if I pay a little more detailed attention to the question it could help me to solve such problems faster. Anyway, moving on.

Now we need to programmatically generate 1001 X 1001 spiral formed in the same way and then calculate the sum on its diagonals. The numbers for this 5 X 5 matrix is 1, 3, 5, 7, 9, 13, 17, 21 and 25. There is obviously going to be some formula to generate this sequence.  Now if we are going to get this numbers by formula we don’t even need a matrix. We can store them in an array and then pick those diagonal numbers according to the formula. So how do I generate the formula? Firstly, I could see there is one variable dependent here which is the level. I mean the level is going to play some role in the formula. So 1 is level 0, 3,5,7 and 9 are level 1 and so on. Another thing which I noticed is that numbers at each level are equal spaced. So numbers at level 1 are spaced by 2 between themselves. Numbers at level 2 are spaced by 4 between themselves and I drew this spiral to two more levels manually to confirm that it was true. So if I find any one of this number I can find the rest of the numbers of that level easily. So find a formula to find at least one number at each level.

Now I was using trial and error to find out the possible formula. Different permutations and combinations. I was clueless for lot of time. Finally, I looked at the spiral and noticed that it is a continuously growing square and we need to calculate the length covered by its borders, so that is the perimeter. I quickly googled the formula for perimeter of a square (I know, I know I should have known that but googling was way faster than thinking about the formula) and it came as 4n where n is the length of a side. So I tried fidgeting with 4n and its variations when I finally reached to the formula 4 X l2 – 2l + 1 to get the first (smallest) number at the level, where l is the level number. Now as mentioned earlier once I get any of the number it is easy to get all other numbers from there. From here I just have to keep on adding 2l to get all the numbers. The formula which I got was a bit complicated so just to simplify the formula I decided to use 4 X l2 + 1 which would give me the second number and then I can get remaining three from them.

We know the number of elements this matrix is going to go have beforehand. For 5 X 5 matrix it is 52 which is 25, so for 1001 X 1001 matrix it is going to be 10012 elements. So we run a loop until the fourth number is less than this 10012 . Fourth number because it is the maximum number for that level. It hardly took around 1/100th of a second to execute this function.

get_the_sum_of_spiral_diagonals = function(n) {
max_number = n^2
total_sum = 1
fourth_number = 0
i = 0
while(fourth_number < max_number) {
  i = i + 1
  second_number = 4 * (i^2) + 1
  first_number = second_number - (2*i)
  third_number = second_number + (2*i)
  fourth_number = third_number + (2*i)
  total_sum = total_sum + first_number + second_number + third_number + fourth_number
 }
return(total_sum)
}

get_the_sum_of_spiral_diagonals(1001)
#[1] 669171001

system.time(get_the_sum_of_spiral_diagonals(1001))
#user  system elapsed
#0.01    0.00    0.01