# Factorial random number generator

Here’s a strange pseudorandom number generator I ran across recently in [1].

Starting with a positive integer n, create a sequence of bits as follows.

1. Compute n! as a base 10 number.
2. Cut off the trailing zeros.
3. Replace digits 0 through 4 with 0, and the rest with 1.

You’d want to use a fairly large n, but let’s use n = 20 for a small example. Then

20! = 2432902008176640000.

Lopping off the trailing zeros gives

243290200817664

Replacing small digits with 0 and large digits with 1 gives

000010000101110

This is not a practical PRNG, but it does produce a sequence of bits that has good statistical properties.

Several questions naturally arise that will be addressed below.

## How many digits does n! have?

I give two ways to compute the answer in this post.

As an example, if we let n = 8675309, then n! has 56424131 digits.

## How many trailing zeros does n! have?

An equivalent question is what is the largest power of 10 that divide n!. When we write out the integers from 1 to n, there are more multiples of 2 than multiples of 5, so powers of 5 are the limiting resource when looking to divide n! by powers of 10.

Every fifth number is a multiple of 5, so the number of powers of 5 dividing n! is at least the floor of n / 5. But every 25th number contributes an extra factor of 5. And every 125th contributes still another factor, etc. So the number of factors of 5 in n!, and thus the number of factors of 10 in n!, is

This is formally an infinite sum, but the sum is actually finite because all the terms are zero once the index i is so large that

5i > n.

Or in other words, the number of terms in the sum is bounded by log5 n. Now

log 8675309 = 9.9…

and so the “infinite” sum above has only nine non-zero terms when n = 8675309. A quick Python calculation

    sum(floor(8675309/5**i) for i in range(1, 10))

shows that n! has 2168823 trailing zeros. So n! has roughly 56 million digits, and we chop off roughly the last 2 million digits, giving us 54 million digits, which leads to 54 million bits.