- #1

- 3

- 0

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 are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter whatever84
- Start date

- #1

- 3

- 0

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

matt grime

Science Advisor

Homework Helper

- 9,395

- 4

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

- 3

- 0

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

- #5

- 289

- 0

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

Lets take an example:

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

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

// 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

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

- 19

Why limit yourself to 64-bit integers?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.

Share:

- Last Post

- Replies
- 1

- Views
- 2K