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

5ⁱ > n.

Or in other words, the number of terms in the sum is bounded by log₅ 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.

Leading digits

The leading digits are a little biased, because the leading digits of factorials follow Benford's law. When we carry out the procedure at the top of this post, the first digit of n! will be 1, 2, 3, or 4 more often than it will be 5, 6, 7, 8, or 9. The first bit will be biased, the second bit less biased, the third bit even less biased, etc. The bias declines rapidly, and so would have little effect when generating millions of bits.

In practice you could discard the first few bits, though in practice you'd never use this generator in the first place because it's so inefficient.

***

[1] Random Numbers and Computers by Ronand Kneusel, Springer, 2018.

The post Factorial random number generator first appeared on John D. Cook.