1. Multiples of 3 and 5

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.

  • For both approaches use the modulo operator, which is %% in R and % in Python.
  • The modulo operator produces the remainder of an integer division.
  • Since both R and Python are vectorized (a style of computer programming where operations are applied to whole arrays instead of individual elements) you can easily calculate the sum of items that match a specified condition.
  • Arrays can take up a lot of memory when they’re large, so this this is only a useful approach for a small problem like this one. Otherwise, looping through terms is more appropriate.
Subset Approach - R
> x <- c(1:999)
> y <- x[x%%3 == 0 | x%%5 == 0]
> sum(y)
[1] 233168
Subset Approach - Python
> import numpy as np
+ seq = np.arange(0,1000) 
+ print(seq[(seq%3 == 0) | (seq%5 == 0)].sum())
+ #233168
Loop Approach - R
> z <-  0
> for (i in 1:999){
+   if (i%%3 == 0 || i%%5 == 0){
+     z = z + i
+   }
+ }
> z
[1] 233168
Loop Approach - Python
> sum=0
+ for i in range(1000):
+     if i%3 == 0 or i%5 == 0:
+         sum+=i
+         
+ sum
233168

2. Even Fibonacci Numbers

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.

  • Loop through each Fibonacci term and use the modulo operator to check if it’s even.
  • Create a running total of even terms.
  • Stop when the sum exceeds 4,000,000.
Using repeat in R
> x <- 1 # First Value
> y <- 2 # Second Value
> z <- 0 # Starting Point
> a <- 2 # Starting Sum
> 
> repeat {
+   
+   if (z>4000000) break
+       
+   z = x + y
+   x = y
+   y = z
+     if (z%%2 == 0){
+       a = a + z
+    }
+ }
> 
> a
[1] 4613732
Using while in R
> x <- 1 # First Value
> y <- 2 # Second Value
> z <- 0 # Starting Point
> a <- 2 # Starting Sum
> 
> while (z < 4000000) {
+   z = x + y
+   x = y
+   y = z
+     if (z%%2 == 0){
+       a = a + z
+    }
+ }
> 
> a
[1] 4613732
Using while in Python
> x = 1 # First Value
+ y = 2 # Second Value
+ z = 0 # Starting Point
+ a = 2 # Starting Sum
+ 
+ while z < 4000000:
+     z = x + y
+     x = y
+     y = z
+     if z%2 == 0:
+         a+= z
+         
+ a
4613732

3. Largest Prime Factor

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

  • Since the primeFactors() function already exists in R, I chose to not spend time replicating it.
> library(numbers)
> primeFactors(600851475143)
[1]   71  839 1471 6857
> #answer is 6857

4. Largest Palindrome Product

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

Find the largest palindrome made from the product of two 3-digit numbers.

  • Loop through all three digit products. \(100\times100, 100\times101, 100\times102....999\times999\)
  • See if the product is equal to its reverse.
  • Save its value if it is greater then the previously saved value.
Using a Loop in R
> library(stringi)
> 
> a <- 0
> 
> for (i in 100:999){
+   
+   for (x in 100:999){
+     y <- i * x
+     z <- stri_reverse(y)
+     if (y == z && y>a){
+       a <- y
+     }
+   }
+ }
> 
> a
[1] 906609
Reversing an integer in Python
> # Convert an integer to a string
+ # Reverse the string
+ # Convert it back to an integer
+ x = 9001
+ y = int(str(x)[::-1])
+ y
1009
Using a Loop in Python
> a = 0 
+ 
+ for i in range(100,1000): 
+     for x in range(100,1000): 
+         y = i*x
+         z = int(str(y)[::-1])
+         if y == z and y > a:
+             a = y
+     
+ a
906609

5. Smallest Multiple

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?

  • We know the number is divisible by 20, so loop through multiples of 20.
  • Multiples of 20 are divisible by 1, 2, 4, 5, 10, and 20, so we can exclude those.
Using a Loop in R
> #don't need to evaluate 1 2 4 5 10 20
> library(tictoc) # timer
> 
> a = 1
> x = 0
> t = c(3,6,7,8,9,11,12,13,14,15,16,17,18,19)
> 
> tic() # start timer
> while (a<20){
+   a = 6 # start at 6. Check 14 numbers.
+   x = x + 1 # Add 1 to loop
+   z = x * 20 # multiples of 20
+   for (i in t){
+     if (z %% i == 0){
+       a = a + 1 # success when 20
+     }
+   }
+ }
> z
[1] 232792560
> toc() # end timer
32.94 sec elapsed
Using a Loop in Python
  • Python is much faster
> import time
+ 
+ a = 1
+ x = 0
+ t = [3,6,7,8,9,11,12,13,14,15,16,17,18,19]
+ 
+ start = time.time()
+ 
+ while a <20:
+     a = 6  
+     x = x + 1
+     z = x * 20
+     for i in t:
+         if z % i == 0:
+             a = a + 1
+ 
+ print(z)
232792560
> end = time.time()
+ print("Elapsed time in seconds:", end - start)
Elapsed time in seconds: 17.222641706466675
More Elegant Solution

Compute the prime factorization of each number from 1 to 20 and multiply the greatest power of each prime together:

  • \(20 = 2^2 \times 5\)
  • \(19 = 19\)
  • \(18 = 2 \times 3^2\)
  • \(17 = 17\)
  • \(16 = 2^4\)
  • \(15 = 3 \times 5\)
  • \(14 = 2 \times 7\)
  • \(13 = 13\)
  • \(11 = 11\)

The other numbers have lower powers and aren’t shown.

Solution:

\[2^4 \times 3^2 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19 = 232,792,560\]

I used the primeFactors() function to create the following custom function. It will find the solution for any value.

> SmallestMultiple <- function(t){
+   
+   x <- aggregate(data.frame(count = numbers::primeFactors(1)),       
+                  list(value = numbers::primeFactors(1)),
+                  length)
+   
+   #   value  count
+   # 1     1      1 
+   
+   for(i in 2:t){
+     
+     y <- aggregate(data.frame(count = numbers::primeFactors(i)),       
+                    list(value = numbers::primeFactors(i)),
+                    length)
+     x <- rbind(x,y)
+   }
+   
+   # full table of prime factors for each number from 1 to t
+   # and their counts.  ex. 20 = 2 2 5 
+   
+   #   value  count
+   # 1     1      1
+   # ...
+   # 26    2      2 
+   # 27    5      1
+   
+   aa <- aggregate(x$count,       
+                   list(value = x$value),
+                   max)
+   
+   # full table of prime numbers and the max count
+   
+   #   value      x
+   # 1     1      1
+   # 2     2      4
+   # ...
+   # 8    17      1 
+   # 9    19      1
+   
+   # Solution
+   a <- prod(aa$value^aa$x)
+   
+   if(t==1){
+     return(1)
+   } else {
+     return(a)
+   }
+   
+ }
> SmallestMultiple(1)
> SmallestMultiple(6)
> SmallestMultiple(8)
> SmallestMultiple(10)
> SmallestMultiple(20)
> SmallestMultiple(28)
[1] 1
[1] 60
[1] 840
[1] 2520
[1] 232792560
[1] 80313433200

It is much faster than a loop.

> tic()
> SmallestMultiple(20)
> toc()
[1] 232792560
0.04 sec elapsed