Euler Problem 20: Large Integer Factorials

Euler Problem 20 is the third problem that requires special consideration for working with very large 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 very large numbers, beyond the generic capabilities of computers to process. This problem can be solved using a specialised R package and using only base-R code.

Euler Problem 20 Definition

.

For example: .

The sum of the digits in the number is .

Find the sum of the digits in the number 100!

Euler Problem 20 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.

Many computer languages, including R, have special libraries to deal with such large numbers. The GMP Multiple Precision Arithmetic package renders this problem almost trivial.

library(gmp)
digits <- factorialZ(100)
digits <- as.character(digits)
answer <- sum(as.numeric(unlist(strsplit(digits, ""))))

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:

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:

Using a loop, we can use the Reduce function to calculate a factorial, using only additions:

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 when the factorial of 0 or 1 is requested. 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.

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)

This function is most certainly not as fast as the GMP package but it was fun to write and to learn about the mechanics behind arbitrary precision arithmetic at work.

If you like to know how factorials can be used to determine the number of ways a deck can be shuffled the watch this video.

The post Euler Problem 20: Large Integer Factorials appeared first on The Devil is in the Data.