0
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ If $M=2^a5^bL$ where $L$ isn't a multiple of $2$ or $5$, then the number of trailing zeros in $M$ is just $\min\{a,b\}$. So to find a formula, you should start by counting how many times $2$ and $5$ divide your large number. $\endgroup$
    – Greg Martin
    Mar 12, 2016 at 18:42
  • $\begingroup$ @GregMartin But what about power of the M here. Its factorial of a very large number. How to deal with it $\endgroup$
    – mat7
    Mar 12, 2016 at 18:45
  • $\begingroup$ There are ways of finding a huge number (mod $p$) without ever finding the huge number. Basically, every time you multiply, reduce the answer (mod $p$) before multiplying further. Hopefully you know about modular exponentiation (if not, I recommend learning about it); the idea for factorials is similar. $\endgroup$
    – Greg Martin
    Mar 12, 2016 at 18:47
  • $\begingroup$ Unless I'm missing something, the answer for $N=7$ is $0$ because $7^{7!}$ is a power of $7$, hence cannot divide evenly into $10$. $\endgroup$
    – Justin Benfield
    Mar 12, 2016 at 19:17
  • $\begingroup$ @JustinBenfield: There are still factors of $5^{5!}$ and $2^{2!+2\cdot 4!+6!}$. $\endgroup$
    – hmakholm left over Monica
    Mar 12, 2016 at 19:24

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Calculating factorial of 500 is not computable in a computer :(. Unless we take modulo. $\endgroup$
    – mat7
    Mar 13, 2016 at 17:49
  • $\begingroup$ @mat7 Check my answer and say if you have some doubts. $\endgroup$
    – TheRandomGuy
    Mar 14, 2016 at 8:06
  • $\begingroup$ @mat7 This should be the algorithm to implement. It reduces the time consumption. Taking factorials upto 1000 doesn't require much time and unless you are calculating it for real large numbers, the method is considerable. $\endgroup$
    – TheRandomGuy
    Mar 14, 2016 at 8:45
  • $\begingroup$ @mat7 Many programming languages, Java for example, provide big integer arithmetic. The factorial of 500 is computed instantly, but is too long for this comment! $\endgroup$
    – Thumbnail
    Apr 6, 2017 at 9:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.