Middle Square Madness

This week, let’s look at the middle-square method for generating pseudorandom four-digit numbers. First, we start with a four-digit number, such as $9,876.$ If we square it, we get the eight-digit number $97,535,376.$ Our next pseudorandom number is taken from the middle four digits of that square: $5,353.$ And to get the next pseudorandom number, we can square $5,353,$ which gives us $28,654,609,$ the middle four digits of which are $6,546.$

Of course, many four-digit numbers have a square that’s seven digits rather than eight. And in a sequence of middle-square numbers, you also might encounter smaller numbers whose squares have six or fewer digits. In these cases, you can append zeros to the beginning of the square until you have eight total digits, and once again take the middle four digits.

No matter what initial four-digit number you pick, your sequence of pseudorandom numbers will eventually repeat itself in a loop. If you want the longest sequence of such numbers before any repetition occurs, what starting number should you pick? And how many unique numbers are in the sequence?

Mathematically, the middle square pseduorandom operation can be written as the following recurrence $$x_{n+1} = ( x_n \mod 1000000 ) // 100, \, \forall n \geq 1.$$ That is, first take the remainder when dividing by a million then use the integer divisor when dividing by $100.$ The assertion (which makes sense since there are only no more than $100,000$ possible values to take) is that eventually there will be some $n$ such that $$x_{n+1} \in \{ x_1, \dots, x_n \}.$$ This means that for any initial value of $x_1,$ we can generate the sequence of successive iterations of the middle square recurrence, each time checking the stopping criterion above. While there may certainly have been more elegeant techniques, I brute forced my way through to a solution of using $6,239$ as an inital value, which results in sequence of $111$ unique numbers before any repetitions.

Interestingly, though perhaps owing to a benevalent question-crafter more than anything else, there is only one such initial value that yields a sequence of $111$ unique numbers before repetitions, and all other positive integers $n \lt 111$ have at least $3$ initial values that lead to a sequence of $n$ unique values before repetitions. For instance, there are three fixed points of the middle square recurrence, namely $2,500$, $3,792$ and $7,600,$ where each exhibits $$x_2 = (x_1 \mod 1000000) // 100 = x_1.$$ Similarly, there are $3$ initial values that lead to a sequence of $110$ unique values before repetitions, namely $3,416$, $4,655$, and $9,251.$