# Total number of zeros.

1. Mar 19, 2007

### whatever84

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. Mar 19, 2007

### matt grime

Removed wrong answer that ignored the bit in brackets in the OP.

Last edited: Mar 20, 2007
3. Mar 19, 2007

### CRGreathouse

Not that I can think of. Counting internal zeros instead of just number of factors of 5 is hard.

4. Apr 23, 2007

### whatever84

Are there any attempts to figure out how to count the total number of zeros?

5. May 13, 2007

### AlphaNumeric

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.

6. May 15, 2007

### Zurtex

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
End

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
7. Jul 3, 2007

### udwdreams

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!

8. Jul 3, 2007

### udwdreams

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.

9. Jul 3, 2007

### Kummer

You can use a theorem referred to as "Legendre's Theorem"

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

This is based on the consequence that the total number of times $$p$$ (a prime) divides $$n!$$ is:
$$\sum_{k=1}^{\infty} \left[ \frac{n}{p^k} \right]$$. 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:
$$\sum_{k=1}^{\infty} \left[ \frac{n}{p^k} \right]$$

10. Jul 3, 2007

### Hurkyl

Staff Emeritus
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?