Calculating Total Zeros in a Large Factorial: Number Theory Explained

[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!.

 

[matt grime]

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

 

[CRGreathouse]

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

 

[whatever84]

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

 

[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.

 

[Zurtex]

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!.

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, let's call it k, and you're trying to work out the number of 0's in x!, then the obvious algorithm would be:

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.

 

[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!

 

[udwdreams]

Lets take an example:

Also, ultimately multiplication isn't very hard task for computers, so working out x! isn't particularly difficult.

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.

 

[Kummer]

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!.

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]

 

[Hurkyl]

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.

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.

Why limit yourself to 64-bit integers?