Total number of zeros.

  • Thread starter whatever84
  • Start date
  • #1

Main Question or Discussion Point

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

Answers and Replies

  • #2
matt grime
Science Advisor
Homework Helper
9,395
3
Removed wrong answer that ignored the bit in brackets in the OP.
 
Last edited:
  • #3
CRGreathouse
Science Advisor
Homework Helper
2,820
0
Not that I can think of. Counting internal zeros instead of just number of factors of 5 is hard.
 
  • #4
Are there any attempts to figure out how to count the total number of zeros?
 
  • #5
289
0
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
Zurtex
Science Advisor
Homework Helper
1,120
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!.
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:
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:
  • #7
2
0
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
2
0
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.
 
  • #9
291
0
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"

[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]
 
  • #10
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
18
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?
 

Related Threads on Total number of zeros.

Replies
11
Views
48K
Replies
6
Views
3K
  • Last Post
Replies
13
Views
13K
  • Last Post
5
Replies
112
Views
41K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
6
Views
3K
  • Last Post
Replies
2
Views
984
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
2
Views
10K
Top