Legendre’s Formula

There is a theorem in number theory known as Legendre’s Formula. It states that if N is a positive integer and p is a prime number, then the highest power of p that divides N! is given by the following formula

\[e_{p} = \sum_{i = 1}^{\infty}\lfloor{\frac{N}{p^{i}}}\rfloor\]

Translating math to english this reads “The highest power of p that divides N! is the infinite sum of the floor of N divided by p to the current exponent”

We know that the infinite sum will eventually reach a terminal value of 0 as at some point, we will reach a large enough exponent for p that the result of dividing n by p raised to i is less than 1. And taking the floor of any value less than 1 will give us 0. Therefore, we do not need to worry about adding up an infinite amount of quotients unless our N is astronomically large.

Adaptation For Trailing Zeros

This formula will allow us to determine the highest power of p in N!. But what about non-prime values? We can take the prime factorization of our target number and run separate instances of the function. Since 10 is the product of 2 and 5, we can simply take the minimum value returned by running the formula on 2, and then 5.

\[\min(\sum_{i = 1}^{\infty}\lfloor{\frac{N}{2^{i}}}\rfloor,\sum_{i = 1}^{\infty}\lfloor{\frac{N}{5^{i}}}\rfloor)\]

But, knowing that powers of 5 will always be larger than powers of two, the number returned by Legendre’s formula for 5 will always be smaller. Therefore, we can dispense with the minimum function altogether and simply find out how many exponents of 5 divide into the factorial. This will give us the number of trailing zeros.

Example Problems

Trailing zeros in 100!

\[\sum_{i = 1}^{\infty}\lfloor{\frac{100}{5^{i}}}\rfloor) = \lfloor\frac{100}{5}\rfloor + \lfloor\frac{100}{5^{2}}\rfloor = 20 +4 = 24\]

We have 24 trailing zeros in 100!

Trailing zeros in 95!

\[\sum_{i = 1}^{\infty}\lfloor{\frac{95}{5^{i}}}\rfloor) = \lfloor\frac{95}{5}\rfloor + \lfloor\frac{95}{5^{2}}\rfloor = 19 + 3 = 22\]

We have 22 traling zeros in 95!

Trailing Zeros Coding Question

Suppose we want to write a program to find the number of trailing zeros in n!. We can simply translate our algorithm into code. We will use a while loop to iterate until the floor of our number divided by 5 to our current exponent yields zero. While iterating we will track the sum and return it upon termination. Leetcode features this exact question.

def trailingZeroes(self, n: int) -> int:
    power = 1
    sum = 0
    while (n//(5**power) != 0):
        sum+=(n//(5**power))
        power+=1
    return sum

Pranav Ahluwalia

My name is Pranav Ahluwalia. I am a computer scientist, esports athlete, and avid poker player
More About Me