Counting the trailing zeros of the factorial of a number in any number system

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

Let's consider the case when we are in the 10th number system, and then we will see how we can summarize 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 amount:

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

We can summarize it in the following formula:

$$

$$\ sum \ limits_ {i = 1} ^ \ infty {N \ over 5 ^ i}.$$

Why 5? It's simple. The final zero is obtained only when in the composition of factorial the number has 10. Thus, considering the number of tens in factorial, we will know the number of final 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:

$$

$$\ sum \ limits_ {i = 1} ^ \ infty {N \ over 5 ^ i}$$

and

$$

$$\ sum \ limits_ {i = 1} ^ \ infty {N \ over 2 ^ i}.$$

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

The solution to our problem

To calculate the finite zeros of the factorial of a number in a certain number system, I compiled the algorithm below:
')

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

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

$$

$${5 \ over 2} + {5 \ over 4} + {5 \ over 8} + ... = 2 + 1 + 0 + ... = 3.$$

But the deuce met twice in the decomposition of 12, so the end result we divide by 2 and round down to a smaller whole. The result is 1.

Do the same with 3:

$$

$${5 \ over 3} + {5 \ over 9} + ... = 1 + 0 + ... = 1.$$

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

Consider another example.

Let the number N = 16, the number system B = 16. Factorial is 16! = 20922789888000, and 20922789888000 in the 16th system is 130777758000. We see that in the finite number system the factorial of the initial number has three zeros. By decomposing 16 into prime factors, we get 2, 2, 2, 2. Here we have only one unique number, therefore, point 2 is performed only once:

$$

$${16 \ over 2} + {16 \ over 4} + {16 \ over 8} + {16 \ over 16} + {16 \ over 32} + ... = 8 + 4 + 2 + 1 + 0 + ... = 15.$$

In the decomposition, we had four deuces, so the sum of the divisions is divided by 4, rounded to the smaller integer: $$${15 \ over 4} = 3.$

PS Most of the material for the post translated from here . The author is Aditya Ramesh .