Just the Factorials, Ma’am

At some point in high school students are taught about factorials. A fairly simple concept, the factorial of a non-negative whole number is written as n! and defined as the product (that means you multiply the numbers) of all the positive whole numbers less than or equal to that number. So 5! = 5 ⨉ 4 ⨉ 3 ⨉ 2 ⨉ 1 = 120. And we define 0! = 1 by convention.

If that was as far as you went with mathematics in school you likely did very little else with factorials and maybe you’ve forgotten all about them. So hopefully this primer jogs your memory.

Here’s a question though: Can you calculate how many zeroes are at the end of any given factorial?

Before we get to that, let’s just look a bit more at factorial. If you studied computer science in university you likely came across a typical first year programming problem: write a function that calculates n!.

My intention here is to go beyond just calculating factorial and look at some interesting mathematical and programming problems. But we need factorial as background, so let’s press on.

Functions

In terms of defining factorial as a product (as we did in the first paragraph above), we can define factorial mathematically as follows:

$$n!=\begin{cases}1, & n = 0\\ \prod\limits_{i=1}^{n} i, & n \geq 1\end{cases}$$

That’s a fancy way of saying you multiply the numbers from 1 to n together. This leads to a non-recursive solution to factorial which may look something like the following (I am using Swift in scripting form, but other languages will look similar):

#!/usr/bin/swift
// Calculate n!

// Read from command line the value n
let n = Int(CommandLine.arguments[1])!

func factorial(_ n: Int) -> Int {
    var fact = 1
    if n > 0 {
        for i in 1...n {
            fact = fact * i
        }
    }
    return fact
}

let answer = factorial(n)
print("\(n)! = \(answer)")

A quick test from the command line shows:

% ./factorial.swift 0
0! = 1
% ./factorial.swift 1
1! = 1
% ./factorial.swift 5
5! = 120
% ./factorial.swift 20
20! = 243290200817664000

You may have noticed though that 5! = 5 ⨉ 4!, that is, you can calculate the factorial of the next number down, and multiply it by n to get n!. So factorial can be defined recursively. Mathematically it looks like:

$$n!=\begin{cases}1, & n = 0\\ n \cdot (n-1)!, & n \geq 1\end{cases}$$

Educators often use factorial as way to teach recursion; that is, a function that calls itself in order to provide a solution to a problem. Mathematicians also love recursion. In Swift we can implement factorial recursively as follows:

#!/usr/bin/swift
// Calculate n!

// Read from command line the value n
let n = Int(CommandLine.arguments[1])!

func factorial(_ n: Int) -> Int {
    if n > 0 {
        return n*factorial(n-1)
    } else {
        return 1
    }
}

let answer = factorial(n)
print("\(n)! = \(answer)")

A quick test from the command will show the same results as the non-recursive solution. There are optimisations that can be made in both solutions, so you could change the test to be n > 1 since both 0! and 1! give the same answer. And you could, for languages with support, write the entire method in 1 line. I’ve chosen to try and keep it simple so it is easier to explain.

Big Numbers

You may have noticed that factorial quickly gives some very big numbers. Computers are great at this sort of thing, which is why this is a good first-year programming problem. Depending on your system and language you may find you get an error with larger numbers. In fact, with my example, I get an error when I calculate 21!. The issue is that the solution can’t fit in an Integer in Swift; for example, on a 32-bit system, an integer can store any value between -2,147,483,648 and 2,147,483,647. Even with 64-bit you are limited as factorials can be huge.

Many languages have the ability to use BigInt or similar types (here’s an implementation of BigInt for Swift you may like to look at). So you may need to switch to something other than Int to calculate larger factorials. For our examples going forward we will continue with using Int just to simplify the code.

All Those Zeroes

As you play around calculating factorials you may notice you tend to get a lot of zeroes on the end of the results. Here’s the first 30 factorials as an example:

1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5,040
8! = 40,320
9! = 362,880
10! = 3,628,800
11! = 39,916,800
12! = 479,001,600
13! = 6,227,020,800
14! = 87,178,291,200
15! = 1,307,674,368,000
16! = 20,922,789,888,000
17! = 355,687,428,096,000
18! = 6,402,373,705,728,000
19! = 121,645,100,408,832,000
20! = 2,432,902,008,176,640,000
21! = 51,090,942,171,709,440,000
22! = 1,124,000,727,777,607,680,000
23! = 25,852,016,738,884,976,640,000
24! = 620,448,401,733,239,439,360,000
25! = 15,511,210,043,330,985,984,000,000
26! = 403,291,461,126,605,635,584,000,000
27! = 10,888,869,450,418,352,160,768,000,000
28! = 304,888,344,611,713,860,501,504,000,000
29! = 8,841,761,993,739,701,954,543,616,000,000
30! = 265,252,859,812,191,058,636,308,480,000,000

So here’s the big question again: given n!, how many zeroes are on the end of the result?

For example, from above, 11! has 2 zeroes. 17! has 3. 30! has 6.

Depending on your background or thought processes, some may jump ahead to a much better solution. But I thought it would be interesting to go through an obvious solution first, as that gives us interesting problems to solve at each step. So let’s go.

Naive Solution

That’s not meant to be a put-down, but there is an instant solution that may come to mind: calculate n! and count the zeroes on the end of the calculation.

We already have code to calculate n!. We just need code to count how many zeroes are in the result.

There are a number of ways to do this. You could convert the result to a string, and then iterate over the string counting the zeroes at the end (or use an inbuilt function to trim off zeroes, say). Or you could basically divide by 10 and look at the remainder. If the remainder is 0, divide by 10 again. And so on until the remainder is non-zero. At that point you have counted the number of zeroes.

There are likely other solutions, but here’s the first solution using String in Swift:

func numZeroes(_ n: Int) -> Int {
    let string = String(n)
    let trimmed = string.trimmingCharacters(in: CharacterSet.init(charactersIn: "0"))
    return string.count - trimmed.count
}

Basically we convert to a string, trim off any zeroes at the end, and then calculate the difference in the character counts of the original string and the trimmed one.

And here’s the second solution (recursively):

func numZeroes(_ n: Int) -> Int {
    if n%10 == 0 {
        return 1 + numZeroes(n/10)
    } else {
        return 0
    }
}

Basically we recursively divide by 10 until the remainder is non-zero.

Combining the second solution with our factorial code we get something like:

#!/usr/bin/swift
// Determines number of zeroes at the end of n!
// Brute force solution using full n! calculation

// Read from command line the value n
let n = Int(CommandLine.arguments[1])!

func factorial(_ n: Int) -> Int {
    if n > 0 {
        return n*factorial(n-1)
    } else {
        return 1
    }
}

func numZeroes(_ n: Int) -> Int {
    if n%10 == 0 {
        return 1 + numZeroes(n/10)
    } else {
        return 0
    }
}

let fact = factorial(n)
print("Zeroes at end of \(n)! = \(numZeroes(fact))")

Running this we get:

% ./zeroes.swift 3
Zeroes at end of 3! = 0
% ./zeroes.swift 11
Zeroes at end of 11! = 2
% ./zeroes.swift 17
Zeroes at end of 17! = 3

The problem with this solution is it depends on factorial being calculated first, which, as we’ve seen, has size limitations. So using Int on my system, I can’t go beyond 20!. Obviously using BigInt or similar you can calculate larger values.

But this all seems a rather slow way to count the zeroes. Can we do better?

A Better Solution

Step back a moment and let’s look at that table above of factorials. You should notice that at 5! there is 1 zero. Then at 10! there are 2. You get 3 at 15!, and 4 at 20!. But at 25! you get 6. What’s going on?

The number of factors of 10 in n! gives us the zeroes. 10 is made of the product of 5 and 2, so we can look at number of factors of 5 and 2. Looking at the factorial product, once we pass 5!, there is always a 2 to match a 5 (lots of factors of 2, many more than 5), so the number of factors of 5 alone gives us the number of zeroes. In other words the number of times 5 appears as a factor of n! gives us the number of zeroes.

We see our first 5 at 5 in the factorial expansion. Then 10. Then 15. Then 20. At 25, we have 5 ⨉ 5, so we now have an extra factor of 5 to consider.

So to find the number of zeroes we can divide by 5 and truncate the result, then 5², then 5³ etc. and add the count of each value to the number of zeroes. Let’s try an example. Let’s look at 101!.

$$\begin{eqnarray}101 \div 5 &=& 20.2, & \text{so 20 zeroes}\\101 \div 5^2 &=& 4.04, & \text{so 4 zeroes}\\Total = 20 + 4 &=& 24, & \text{so 24 zeroes total}\end{eqnarray}$$

If we actually use our factorial code above to calculate 101! we get:

101! = 9425947759838359420851623124482936749562312794702543768327889353416977599316221476503087861591808346911623490003549599583369706302603264000000000000000000000000

Which has 24 zeroes (I counted them by hand).

An alternative way to write the algorithm, which may be easier to implement, is to divide by 5, then divide the result by 5 again, and then again, and so on, until the result is less than 5. So:

$$\begin{eqnarray}101 \div 5 &=& 20.2, & \text{so 20 zeroes}\\20 \div 5 &=& 4, & \text{so 4 zeroes}\\Total = 20 + 4 &=& 24, & \text{so 24 zeroes total}\end{eqnarray}$$

We can implement that in code fairly easily. Here’s a recursive solution:

#!/usr/bin/swift
// Determines number of zeroes at the end of n!
// Fast solution

// Read from command line the value n
let n = Int(CommandLine.arguments[1])!

func factorialZeroes(_ n: Int) -> Int {
    if n < 5 {
        return 0
    } else {
        return n/5 + factorialZeroes(n/5)
    }
}

print("Zeroes at end of \(n)! = \(factorialZeroes(n))")

Let’s try some examples:

% ./zeroes2.swift 20
Zeroes at end of 20! = 4
% ./zeroes2.swift 101
Zeroes at end of 101! = 24
% ./zeroes2.swift 1234
Zeroes at end of 1234! = 305
% ./zeroes2.swift 9876543
Zeroes at end of 9876543! = 2469132

Amazing right?! Imagine trying to do a large number like 9876543! by actually calculating the factorial!

Here’s a bonus. If you want to do this non-recursively, it is fairly easy. But it would be useful if we knew the maximum \(x\) in \(5^x\) to divide by.

We know \(5^x < n\), as we can’t divide by something larger than n. Taking log base 5 of both sides this means:

$$\begin{eqnarray}5^x &<& n\\log_5 5^x &<& log_5 n\\xlog_5 5 &<& log_5 n\\x &<& log_5 n\end{eqnarray}$$

So the floor of \(log_5 n\) (meaning the largest whole number less than \(log_5 n\)) gives us the maximum power of 5 to use in our loop. We can then implement a non-recursive solution as:

#!/usr/bin/swift
// Determines number of zeroes at the end of n!
// Fast solution

import Foundation

// Read from command line the value n
let n = Int(CommandLine.arguments[1])!

func factorialZeroes(_ n: Int) -> Int {
    var count = 0
    for i in 1...Int(floor(log(Double(n))/log(5.0))) {
        count = count + n/Int(pow(5.0,Double(i)))
    }
    return count
}

print("Zeroes at end of \(n)! = \(factorialZeroes(n))")

Note that Swift doesn’t have a function for log base 5, but does for natural log. So to calculate an arbitrary log values you basically divide the natural log of the value by the natural log of the base. Hence the code above.

I hope that was informative and also a bit of fun. For those who read all the way through this, I thought I’d end with a little maths humour. Thanks for reading.

Calculate

230 – 220 ÷ 2

You probably won’t believe me,
but the answer is 5!