Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Total number of zeros.

  1. Mar 19, 2007 #1
    Hi all,

    Is there any number theory for calculating the total number of zeros ( NOT only the right zeros) in a big factorial without calculating the whole n!.
  2. jcsd
  3. Mar 19, 2007 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Removed wrong answer that ignored the bit in brackets in the OP.
    Last edited: Mar 20, 2007
  4. Mar 19, 2007 #3


    User Avatar
    Science Advisor
    Homework Helper

    Not that I can think of. Counting internal zeros instead of just number of factors of 5 is hard.
  5. Apr 23, 2007 #4
    Are there any attempts to figure out how to count the total number of zeros?
  6. May 13, 2007 #5
    Though it's utterly off the top of my head, could you do something with mod 10^n ?

    For instance, if X mod 10^n = X mod 10^(n+1) then the n+1'th entry in X is 0. For instance, 301 mod 100 = 1 = 301 mod 10, so the 2nd entry of 301 is zero.

    Unfortunately that's about the limit of my understanding of mods which aren't prime other than phrases like "Chinese Remainder Theorem". I imagine you could write a computer program to do the method I just suggested but it'd be much more convoluted than just computing n! and counting zeros.
  7. May 15, 2007 #6


    User Avatar
    Science Advisor
    Homework Helper

    Lets take an example:

    20! = 2432902008176640000

    Therefore 20! has 7 0's.

    Now it's easy enough to calculate the fact it has 4 end 0s, but the real question is it computationally efficient to consider looking at each of the other digits rather than just explicitly working it out.

    Maybe, say you have the number of end 0's, lets call it k, and you're trying to work out the number of 0's in x!, then the obvious algorithm would be:

    Code (Text):

    For i = (k + 1) to (Floor[Log_10(x!)] - 1)
       If Number of digits (x! mod 10^i) < i
          counter = counter + 1
       End If

    Number of Zeros = counter + k
    Obviously that's not a very efficient code. There are easy improvements you can make, like coming up with your own algorithm to work out x! mod 10^i, easy enough to make quite efficient, also the Log function has some obvious properties making Log_10(x!) very easy to work out. Actually, for very large x, you may want to look at stirlings approximation ( http://mathworld.wolfram.com/StirlingsApproximation.html ) and see if it's accurate enough.

    But even so, you have to work out almost x!, with x! mod 10^(number of digits of x - 1), so I'm not sure it'd be any quicker at all, you'd need to test it. Also, ultimately multiplication isn't very hard task for computers, so working out x! isn't particularly difficult.
    Last edited: May 15, 2007
  8. Jul 3, 2007 #7
    number of trailing zeroes

    // computes number of trailing zeroes in n!
    int TrailingZeros(int n) {
    int num = 0;
    while (n >= 5) {
    n /= 5;
    num += n;
    return num;

    The idea is that number factors 5 in p! / (5p)! is p. You can prove this by recurrence. Thus, you do not need to compute p!
  9. Jul 3, 2007 #8
    Working out x! is impossible for x large. 100! does not fit on an integer. Even using 64-bit integer won't take you very far if you need to compute N!
    the program you have would overflow very quickly and return invalid results.
  10. Jul 3, 2007 #9
    You can use a theorem referred to as "Legendre's Theorem"

    [tex]n! = \prod_{p\leq n} p^{\sum_{k=1}^{\infty} [ n/p^k] }[/tex]

    This is based on the consequence that the total number of times [tex]p[/tex] (a prime) divides [tex]n![/tex] is:
    [tex]\sum_{k=1}^{\infty} \left[ \frac{n}{p^k} \right][/tex]. So the number of zero's the the minimum of the number of times 2 divides n! and 5 divides n! since 10 = 2*5. Furthermore, since 5>2 it means that the smaller number is the number of times 5 divides n!.
    And so by Legendre's formula we have:
    [tex]\sum_{k=1}^{\infty} \left[ \frac{n}{p^k} \right][/tex]
  11. Jul 3, 2007 #10


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Both of you should look at the opening post again; you answered the question that the opening poster specifically said he did not want answered.

    Why limit yourself to 64-bit integers?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook