Trailing zeroes in product of numbers with factorial power

Question

I need to find the number of trailing zeroes in $1^{1!} \cdot 2^{2!} \cdot 3^{3!} \cdots N^{N!}$, where $N$ is natural number.

Assuming $N$ is very large, say $500$, where you cannot find factorial of a number. Also, I need to answer by taking modulo with $100000007$.

If $N$ was small then we can simply factorise each number, and see power of $2$ and power of $5$. Whatever is small will be count of trailing zeroes. But how to solve this one ?

EXAMPLE : For $N=7$ answer is $120$, after taking modulo given prime, that is $100000007$.

How to find it for given $N$? What should be algorithm for the same. If there is direct some mathematical formula, then it would be more awesome.

Answer 1

I am just showing you an algorithm. I thought of it.

twos = 0
fives = 0

For n in numbers from 1 to n:

    a = (number mod 2 == 0)
    b = (number mod 5 == 0)

    if a or b:
        k = factorial(n)

        if a == True:
            twos = twos + (number of times 2 can be divided from n)*k

        if b == True:
            fives = fives + (number of times 5 can be divided from n)*k


print(min(twos, fives) mod 100000007)

It fits with the test case you gave of n = 7. I advise you not to use a recursive implementation of factorial. One of dynamic programming or a for loop would do.

Explanation: This algorithm finds out the number of 2's and 5's in the numbers prime factorisation. You might find the '(number of times 2 can be divided from n)*k' strange but this is actually due to the fact that some numbers like 4, 10 & 25 have many 2's and 5's in their factorisation. If you are wondering about a and b then just imagine that there are some numbers which aren't divisible by 2 or 5 and finding their factorial would be a total waste of time and may increase the time expense. The simple 'or' is a binary logic gate. a and b are Booleans.

I wrote simple code to find the solution to your problem without using my algorithm and it stuck at 10. You will have to employ this algorithm to be able to find the answer.

Hope you found that useful.