Project Euler 20: Factorial Digit Sum
Peter Prevos |
560 words | 3 minutes
Share this content
Project Euler 20 is the third problem that requires special consideration for working with huge integers. In this problem, we look at factorials. These numbers are useful in combinatorics if, for example, you like to know in how many ways you can arrange a deck of cards.
The problem with computing factorials is that they are mostly vast numbers, beyond the generic capabilities of computers to process. For example, a humble pack of playing cards can be shuffled in \(52! = 80658175170943878571660636856403766975289505440883277824000000000000\) different configurations.
The largest number traditional handheld calculators can factorise is the mythical number 69.
Project Euler 20 Definition
\(n!\) means \(n \times (n − 1) \times \ldots \times 3 \times 2 \times 1\)
For example, \(10! = 10 \times 9 \times \ldots \times 2 \times 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!
Proposed Solution
The factorial of the number 100 contains 158 digits, which is a lot more digits than a 64-bit operating system can accurately produce. Using the standard function: factorial(100) = 9.332622e+157. Without using a specialised algorithm, we cannot determine the sum of all digits. We need to deploy arbitrary-precision arithmetic to solve this problem.
This problem can be solved using a specialised R package and using only base-R code. Many computer languages, including R, have special libraries to deal with such large numbers. The GMP package renders this problem almost trivial.
## Project Euler 20: Factorial Digit Sum
library(gmp)
digits <- factorialZ(100)
digits <- as.character(digits)
answer <- sum(as.numeric(unlist(strsplit(digits, ""))))
print(answer)Using base-R code
The problem becomes more interesting when only using basic R code. I developed the big.add function to solve Euler Problem 13 through the addition of very large integers. We can extend this function to also calculate factorials. A factorial can be replaced by a series of additions, for example:
$$3! = 1 \times 2 \times 3 = (((1+1) + (1+1)) + (1+1))$$
This can be mimicked in R using the Reduce function. This function reduces a vector to a single value by recursively calling a function. Reduce("+", rep(4, 5)) is the same as:
$$4 \times 5 = ((((4 + 4) + 4) + 4) + 4) = 20$$
Using a loop, we can use the Reduce function to calculate a factorial, using only additions:
## Base-R Code
fact <- 1
x <- 100
for (i in 2:x) {
fact <- Reduce("+", rep(fact, i))
}
print(fact)
The big.factorial() function below implements this idea by combining the big.add() and Reduce() functions to calculate large integer factorials. The function returns a value of 1, for factorial of 0 or 1. This function does not calculate the Gamma-function for fractions. For all other values, it goes through a loop from 2 to the requested factorial. The temporary values are stored in the bf variable. The code loops through the factorials by using the result of the previous Reduce call into the current one.
source("problem013.R", echo = FALSE)
big.factorial <- function(x) {
x <- floor(x)
bf <- 1
if (x > 1) {
for (i in 2:x) {
bf <- Reduce(big.add, rep(bf,i))
}
}
return (bf)
}
digits <- big.factorial(100)
answer <- sum(as.numeric(unlist(strsplit(as.character(digits), ""))))
print(answer)Share this content
