16. Power Digit Sum

\(2^{15}\) = \(32,768\) 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}\)?

Calulate in R
> library(gmp)
> library(stringr)
> 
> pow.bigz(2,1000) %>% as.character() %>% 
+   str_split("") %>% .[[1]] %>% as.integer() %>% sum()
[1] 1366
Calculate in Python
> sum(map(int, str(2**1000)))
1366

17. Number Letter Counts

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 \(1,000\) (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.

Loop Approach - R
  • Start with numbers_to_words().
> library(xfun)
> 
> numbers_to_words(342)
[1] "three hundred forty-two"
> #remove "-" and spaces. calculate length.
> x <- numbers_to_words(342) %>% str_replace("-","") %>% 
+   str_replace_all(" ","") %>% str_length()
> x
[1] 20
  • Need to add “and” to most values over 100.
> Num_to_1000 <- function(x){
+   
+   y <- numbers_to_words(x) %>% str_replace("-","") %>% 
+     str_replace_all(" ","") %>% str_length()
+   
+   # Add "and"
+   if(x%/%100 >0 && x%%100!=0){
+     y = y+3
+   }
+ return(y)
+ }
> 
> Num_to_1000(342)
[1] 23
  • Loop through.
> z = 0
> for (i in 1:1000){
+   z = z+Num_to_1000(i)
+ }
> 
> z 
[1] 21124
Loop Approach - Python
  • Python’s num2words already includes “and.”
> from num2words import num2words
+ num2words(342)
'three hundred and forty-two'
> len(num2words(342).replace(" ","").replace("-",""))
23
> x = 0
+ for i in range(1,1001):
+     x+= len(num2words(i).replace(" ","").replace("-",""))
+     
+ x
21124

18. Maximum Path Sum I

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\).

That is, \(3 + 7 + 4 + 9 = 23\).

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

NOTE: As there are only \(16,384\) 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!

The optimal solution involves dynamic programming.

You must find the maximum value at each level starting from the bottom. For example, using the sample triangle:

3
7 4
2 4 6
8 5 9 3

Level 3 becomes:
max(2+8,2+5)
max(4+5,4+9)
max(6+9,6+3)

3
7 4
10 13 15

Level 2 becomes:
max(7+10,7+13)
max(4+13,4+15)

3
20 19

Level 1 becomes:
max(3+20,3+19)

23

Solution in R
> x = "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"
  • First split into 15 rows and split each by spaces
> #Split by line (\n) and then by space
> y <- str_split(x,"\n") %>% .[[1]] %>% str_split(" ")
> 
> #Create 15 x 15 matrix of zeros to place values
> z <- matrix(0,nrow=15, ncol=15)
  • I then moved the values into a matrix (as integers).
> # Move the integer values into the Matrix
> 
> for (i in rev(1:15)){
+   
+   for (b in 1:length(y[[i]])){
+     
+     z[i,b] <- as.integer(y[[i]][b])
+     
+   }
+ }
> 
> z 
      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13]
 [1,]   75    0    0    0    0    0    0    0    0     0     0     0     0
 [2,]   95   64    0    0    0    0    0    0    0     0     0     0     0
 [3,]   17   47   82    0    0    0    0    0    0     0     0     0     0
 [4,]   18   35   87   10    0    0    0    0    0     0     0     0     0
 [5,]   20    4   82   47   65    0    0    0    0     0     0     0     0
 [6,]   19    1   23   75    3   34    0    0    0     0     0     0     0
 [7,]   88    2   77   73    7   63   67    0    0     0     0     0     0
 [8,]   99   65    4   28    6   16   70   92    0     0     0     0     0
 [9,]   41   41   26   56   83   40   80   70   33     0     0     0     0
[10,]   41   48   72   33   47   32   37   16   94    29     0     0     0
[11,]   53   71   44   65   25   43   91   52   97    51    14     0     0
[12,]   70   11   33   28   77   73   17   78   39    68    17    57     0
[13,]   91   71   52   38   17   14   91   43   58    50    27    29    48
[14,]   63   66    4   68   89   53   67   30   73    16    69    87    40
[15,]    4   62   98   27   23    9   70   98   73    93    38    53    60
      [,14] [,15]
 [1,]     0     0
 [2,]     0     0
 [3,]     0     0
 [4,]     0     0
 [5,]     0     0
 [6,]     0     0
 [7,]     0     0
 [8,]     0     0
 [9,]     0     0
[10,]     0     0
[11,]     0     0
[12,]     0     0
[13,]     0     0
[14,]    31     0
[15,]     4    23
  • I then created a matrix to store the max values by row.
  • After one row of max values was calculated they were moved into the original matrix. That’s why it is dynamic programming. The solution to each level depends on the prior level.
> # Matrix of zeros to store max values
> t <- matrix(0,nrow=14, ncol=14)
> 
> for (i in rev(1:14)){
+   
+   # Calculate Max values
+   for (b in 1:length(y[[i]])){
+     
+     t[i,b] <- max(z[i,b]+z[i+1,b],z[i,b]+z[i+1,b+1])
+   }
+   
+   # replace values in original Matrix with calculated max values
+   
+   for (b in 1:length(y[[i]])){
+     
+     z[i,b] <- t[i,b]
+   }
+ }
> 
> z[1:14,1:14]
      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13]
 [1,] 1074    0    0    0    0    0    0    0    0     0     0     0     0
 [2,]  995  999    0    0    0    0    0    0    0     0     0     0     0
 [3,]  818  900  935    0    0    0    0    0    0     0     0     0     0
 [4,]  704  801  853  792    0    0    0    0    0     0     0     0     0
 [5,]  686  640  766  731  782    0    0    0    0     0     0     0     0
 [6,]  666  614  636  684  660  717    0    0    0     0     0     0     0
 [7,]  647  501  613  609  533  657  683    0    0     0     0     0     0
 [8,]  559  499  479  536  514  526  594  616    0     0     0     0     0
 [9,]  460  434  419  475  508  470  510  524  487     0     0     0     0
[10,]  419  365  393  387  419  425  430  376  454   322     0     0     0
[11,]  378  317  231  321  354  372  393  354  360   293   247     0     0
[12,]  325  246  187  178  256  329  273  302  263   242   193   233     0
[13,]  255  235  154  150  140  179  256  209  224   172   174   176   148
[14,]  125  164  102   95  112  123  165  128  166   109   122   147   100
      [,14]
 [1,]     0
 [2,]     0
 [3,]     0
 [4,]     0
 [5,]     0
 [6,]     0
 [7,]     0
 [8,]     0
 [9,]     0
[10,]     0
[11,]     0
[12,]     0
[13,]     0
[14,]    54
  • The top value is the solution.
> z[1,1] # Solution
[1] 1074

19. Counting Sundays

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

Loop Approach in R
> library(lubridate)
> #Sunday is 1
> wday("2020-10-25")
[1] 1
  • Loop through years and months.
> c = 0
> 
> for (i in 1901:2000){
+   
+   for (b in 1:12){
+     if (wday(str_c(as.character(c(i,b,1)),collapse = "-"))==1){
+     
+       c = c + 1
+       
+     }
+   }
+ }
> 
> c
[1] 171
Loop Approach - Python
> from datetime import date
+ from collections import Counter
+ 
+ date(2020,10,25).weekday()
+ # 6 is Sunday
6
> c = 0
+ 
+ counter = Counter()
+ 
+ for i in range(1901,2001):
+     for b in range(1,13):
+         day = date(i,b,1)
+         counter[day.weekday()]+=1
+             
+ counter
Counter({4: 173, 2: 173, 0: 172, 1: 171, 5: 171, 6: 171, 3: 169})
> counter[6]
171

20. Factorial Digit Sum

\(n!\) means \(n × (n − 1) × ... × 3 × 2 × 1\)

For example, \(10! = 10 × 9 × ... × 3 × 2 × 1 = 3,628,800\), 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!\)

Solution in R
> gmp::factorialZ(100) %>% str_split("") %>% .[[1]] %>% 
+   as.integer() %>% sum()
[1] 648
Solution in Python
> import math
+ sum(map(int, str(math.factorial(100))))
648