Counting trailing zeros of factorial numbers in any number system

How can I calculate the number of trailing zeros of the factorial of a number in a certain number system?

Let's look at the case when we are in the 10th number system, and then see how we can generalize this into a universal solution. We are given the number N and for its factorial we need to find the number of trailing zeros. The solution will be quite simple - the sum:

Math.floor(N/5) + Math.floor(N/25) + Math.floor(N/125) + Math.floor(N/625) + ...

We can generalize it into such a formula:

$$

Why 5? It's simple. The final zero is obtained only when the number has 10 in the factorial. Thus, counting the number of tens in the factorial, we find out the number of finite zeros.

Why in the example above we divide by 5? Because 10 can be obtained by multiplying 5 by 2. Therefore, the complete solution will have two formulas:

$$

and

$$

But, reasoning logically, we know that the first amount will be less, so we only need to calculate it (more details can be found here ).

Solution to our problem

To calculate the final zeros of the factorial of a number in a specific number system, I compiled the algorithm below:

1. Factor the number B of the number system.
2. Divide the number N by each unique prime factor K, multiplying K by itself until $$ will be more than one, while rounding each result to a smaller integer.
3. If, when expanding the number of the number system, we get several identical prime factors K, then we should divide the result above by the number of identical K.
4. Of all the divisions of N by each unique factor K, choose the smallest quotient, which will be our answer.

I will show it with an example.
Let the number N = 5, the number system B = 12. Factorial 5! = 120, and 120 in the 12th system is A0. We see that in a finite number system the factorial of the original number has one zero. If we decompose 12 into prime factors, we get 2, 2, 3. We have two unique numbers: 2 and 3. Following our algorithm, we will fulfill point 2 with the number 2.

$$

But the deuce met twice in the decomposition of 12, so we divide the final result by 2 and round to a smaller integer. As a result, we get 1.

We do the same with 3:

$$

Thus, we have obtained two quotients of divisions of the number N by prime factors of the number of the number system. They are both equal to 1, so we don’t have to choose the smaller one and we just give the answer - 1.

Consider another example.

Let the number N = 16, the number system B = 16. The factorial 16! = 20922789888000, and 20922789888000 in the 16th system - 130777758000. We see that in the final number system the factorial of the original number has three zeros. If we decompose 16 into prime factors, we get 2, 2, 2, 2. Here we have only one unique number, therefore, item 2 is executed only once:

$$

When we decomposed, we had four deuces, so we divide the sum of divisions by 4 with rounding to a smaller integer: $$

PS Most of the material for the post translated from here . Posted by Aditya Ramesh .