Last week I wrote about a mental random number generator designed by George Marsaglia. It’s terrible compared to any software RNG, but it produces better output than most people would if asked to say a list of random digits.

Marsaglia’s RNG starts with a two-digit number as a seed state, then at each step replaces n with the 10s digit of n plus 6 times the 1s digit. Here’s the generator in Python form, taken from the earlier post.

state = 42 # Set the seed to any two digit number

def random_digit():
    tens = lambda n: n // 10
    ones = lambda n: n % 10
    global state
    state = tens(state) + 6*ones(state)
    return ones(state)

Only the last digit of the state is returned: the state has two digits but the output has one digit.

Alexander Janßen left an interesting comment on Mastodon regarding the generator:

I’m not sure if it’s already documented anywhere, but a random seed of 59 sticks and always returns a 9. This is similiar to the initial state of 0 (which is more trivial). In return that means, that the state 59 is never reached from any other sequence.

To explore this further, let’s look at just the states of the mental RNG, not the output digits.

If you start with the state 1, you will produce each of the numbers from 1 to 58 in a cycle. It follows that if you start at any number between 1 and 58 you’ll produce the same sequence of states in a cycle, though starting at a different point in the cycle.

… → 1 → 6 → 36 → 39 → … → 1 → …

If you start at 59, you’ll stay at 59 because 5 + 6×9 = 59. In this case, the RNG literally does what is described in the Dilbert cartoon below.

Over here we have our random number generator. nine nine nine nine nine nine ...

Collatz interlude

If you start with a seed larger than 59, you’ll eventually land on a state less than 59, and then produce the same cycle as described above. This is reminiscent of the Collatz conjecture, which I describe here as follows.

The Collatz conjecture asks whether the following procedure always terminates at 1. Take any positive integer n. If it’s odd, multiply it by 3 and add 1. Otherwise, divide it by 2. For obvious reasons the Collatz conjecture is also known as the 3n + 1 conjecture.

The Collatz conjecture remains an open question, though there has been some progress on the problem. I routinely get email from people who say they have no training in math but believe they have solved the problem. Recently they have begun to explain how an LLM led them to their proof.

Does the Collatz sequence get stuck in a cycle for some starting point? Nobody knows. But we can show every starting point for Marsaglia’s mental RNG ends up in a cycle.

Back to Marsaglia

If we start the mental RNG with 99, we next get 63, and then 24. So starting at 99, we end up in a cycle after two steps. The same is true starting at 69 or 89. Otherwise, any starting point between 60 and 98 leads us to a cycle after one step.

Marsaglia’s generator is supposed to be seeded with a two-digit number. What if we seed it with a larger number? For example, what if we start at 1066 and consider the 1os “digit” to be 106?

Each step of the algorithm reduces the state by an order of magnitude, and so if we start with a state greater than 1000, we eventually get to a state less than 1000. Then every state between 100 and 1000 leads to a cycle, usually the permutation of the digits 1 through 58, but the following three-digit states lead to the fixed point of 59.

118, 177, 236, 295, 354, 413, 472, 531, 590

Related posts

The post Cycles in Marsaglia’s mental RNG first appeared on John D. Cook.

Previous Post
Next Post