Trailing zeroes

To solve this challenge, we will first write out some values for \(n!\) and to see if a pattern arises.

As we might expect, the factorial function grows exceedingly fast. However, let's now take a look at how many trailing zeroes there are for each value of \(n\):

Now the more mathematically inclined among you may try to find this sequence on the OEIS, and doing so would yield the sequence A027868 "Number of trailing zeros in \(n!\)", where the formula to solve for \(f(n)\) is listed in both summation and closed form. However that's cheating, so forget that for now. We're going to derive a solution ourselves.

We note that for each multiple of \(5\), the number of trailing zeroes in \(n!\) seems to initially increase by 1. We go from \(0 \to 1\) when we go from \(n=4 \to n=5\). Next we go from \(1 \to 2\) when going from \(n=9 \to n=10\), and so on.

However this pattern breaks when we reach \(n=25\), where we jump from \(4\) trailing zeroes to \(6\). What's going on here?

Well, let's write out the product form of some of these values. We'll focus on the values where the number of trailing zeroes increases, as well as the value of \(n-1\) and \(n+1\).

At first glance, the product forms don't reveal a dramatic pattern. However, if we express these factorials in their prime factorisation form, an interesting pattern emerges.

We can now begin to see that the values for where the trailing zero count increases, so too does the exponent \(x\) in the \(5^x\) term. In fact, the key to cracking this challenge is the exponent \(x\) in the \(5^x\) term. In other words, the number of trailing zeros is exactly the number of factors of \(5\) in the factorial. This makes sense because as soon as we hit \(n=5\), we now have at least one factor of \(2\) and at least one factor of \(5\), in other words \(2 \cdot 5\), or \(10\). For all \(n \geq 5\), the result of \(n!\) will always have at least one trailing zero! A factor of \(10\) will always be hidden in there.

This also explains the jump from \(f(n)=4\) when \(n=24\), to \(f(n)=6\) when \(n=25\). This is because \(25\) is equal to \(5^2\), so we not only introduce one factor of \(5\), but two. Writing out the prime factorisation of \(24!\) and \(25!\) helps us see this more clearly:

Since the exponent increased by \(2\), so too does the number of trailing zeroes.

The way to solve this challenge is to remove each power of \(5\), counting how many times we did so. This means that the number of trailing zeroes is equal to the following series:

Where \(k\) is the largest integer power of \(5\) that does not exceed \(n\). More succinctly, it can be expressed as the following summation:

Let's try an example of this. We know that \(5! = 12\underline{0}\), so \(f(5) = 1\). Plugging in our values to the series gives:

Since the next power of \(5\) (which would be \(25\)) exceeds \(n=5\), we just have the one term which evaluates to \(1\).

Now we'll try \(25!\), which equals \(15511210043330985984\underline{000000}\). This has \(6\) leading zeroes, and so \(f(25) = 6\). We'll write out the series, stopping at the point where we the power of \(5\) exceeds \(25\):

One way (among many) to achieve this in C# would be like so:

int TrailingZeroes(int n)
{
    int result = 0;

    for (int k = 1; ; k++)
    {
        int power = (int)Math.Pow(5, k);
        if (power > n)
            break;
        
        result += n / power;
    }
    
    return result;
}

Alternatively, to keep the break condition within the definition of the for loop, we can iterate \(\lfloor \log_{5}(n) \rfloor\) times inclusive, as seen in \((1)\). The following implementation is effectively identical, although it does require an addition Math.Log call:

int TrailingZeroes(int n)
{
    int ubound = (int)Math.Log(n, 5);
    int result = 0;

    for (int k = 1; k <mark><=</mark> ubound; k++)
    {
        result += (int)(n / Math.Pow(5, k));
    }
    
    return result;
}

If you're content with this solution, go ahead and call it here. However we're not done quite yet. There exists another solution!

First, consider that any integer \(n\) can be expressed in base \(5\) as:

The sum of the digits¹ in base \(5\) can therefore be expressed as:

If we perform integer division by \(5\), notice that we find:

Similarly:

Since the trailing zero count is defined to be of the series \((1)\), we can substitute the expressions we have:

For each \(i\) from \(1\) to \(k\), the inner sum is a geometric series:

Therefore \(f(n)\) can be expressed as:

Multiplying both sides by \(4\) gives:

Notice that:

• \(\sum_{i=1}^k a_{i} \cdot 5^i = n - a_{0}\), since \(n = a_{0} + \sum_{i=1}^k a_{i} \cdot 5^i\)
• and \(\sum_{i=1}^k a_{i} = s_{5}(n) - a_{0}\)

Thus:

Finally, dividing by \(4\) gives us:

This also leads to an interesting identity:

Which makes sense, because every power \(5^k\) is simply one more than a multiple of \(4\). For example \(5^1 = 5 = 4 + 1\), \(5^2 = 25 = 4(6) + 1\), \(5^3 = 4(31) + 1\), etc.

A C# function to sum the digits in base 5 looks something like this:

int SumOfBase5Digits(int n)
{
    int sum = 0;
    while (n > 0)
    {
        sum += n % 5;
        n /= 5;
    }
    return sum;
}

Which means the TrailingZeroes function can be essentially one-lined:

int TrailingZeroes(int n)
{
    return (n - SumOfBase5Digits(n)) / 4;
}

I don't believe it's possible to express the solution without some kind of loop (either the summation of \(\frac{n}{5^k}\) terms given by \((1)\), or the sum of the digits given by \((2)\)). This seems to imply that the lower bound is \(\Omega(\log n)\). However, if anyone stumbles across a solution that can be performed in \(\Omega(1)\) time, please do let me know!

As I was solving this challenge myself (which I always do to ensure it is in fact solvable), I also managed to write up an incredibly cursed one-liner. To anyone who wishes to understand it: Good. Luck.

int TrailingZeroes(int n) => Enumerable.Range(1, n).SelectMany(n => Enumerable.Range(2, n-1).Aggregate((rem: n, facs: new List<int>()), (s, i) => { while(s.rem % i == 0){ s.facs.Add(i); s.rem /= i; } return s; }).facs).Count(n => n == 5);