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.
- Compute n! as a base 10 number.
- Cut off the trailing zeros.
- 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
log5 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.
What about using the the BBP algorithm to compute hex digits of PI starting at some random n-th digit ? BBP C-code is fairly easily to set up, perhaps even easier in Python.
https://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula