A problem from Knuth's The Art of Computer Programming about middle square method This isn't a 'homework' question or anything similar - just for my own personal interest.
In his discussion of random numbers (vol 2),Knuth poses this question:
Prove that the middle-square method using 2n-digit numbers to the base b has the following disadvantage: if the sequence includes any number whose most significant n digits are zero, the succeeding numbers will get smaller and smaller until zero occurs repeatedly.
(He rates this as '14' which I take to mean it should take somewhat less than 10 minutes - but I'm really struggling with it.)
A quick explanation: the middle-square method is a naive (though actually first suggested by none other than John von Neumann) random number generation method where we take a number n-digits long, square it and take the middle n-digits as our next seed or random number.
But, actually, it looks to me that it's not too difficult to show an example where Knuth’s proposition appears to be false.
Let n=2, b=10 and the seed number be 60
Then every subsequent number in the sequence is also 60 (obviously that’s as useless as repeated zeros for a random number generator.)
But maybe using n=2  is a bit silly, so let’s look at the general case.
Any (base-b ) integer is then of the form $ b^n - x $ where $ 0<x<b^n $, but I think that without any restriction to the generality of we can look at $ b^n-1 $, the largest number we can have (and therefore the one that will produce the maximum number of digits when squared.)
So we get $ b^{2n}-2b^n+1 $ as the square.
Now we need to get the middle digits so we lose the right $\frac{n}{2}$ digits by dividing by $b^{\frac{n}{2}}$:
$\frac{b^{2n}-2b^n+1}{b^{\frac{n}{2}}} = b^{\frac{3n}{2}}-2b^{\frac{n}{2}}+\frac{1}{b^{\frac{n}{2}}}$
In the general case that final term would be $\frac{x^2}{b^{\frac{n}{2}}}$ and the biggest that could be is $x\rightarrow b$ but as the smallest n  can be is 2, this term dwindles very rapidly indeed compared to the others as n  increases.
So we can ignore the final term and are left with $b^{\frac{3n}{2}} - 2b^{\frac{n}{2}}$, but we still have up to $ \frac{n}{2} $ too many significant digits here – so we need to get rid of them too.
What we are now looking for is the remainder when we divide our current result by $b^{\frac{3n}{2}} - 1 - (b^n-1)  = b^{\frac{3n}{2}}-b^n $
This is where I just run out of puff. How do I do that, and given the complexity of this approach and Knuth's view that it's a relatively simple proof - have I taken a wrong turn somewhere here?
 A: Your example doesn't make Knuth's proposition false. In fact, Knuth talks about the mid-square method with $2n$-digit numbers. So we use a $2n$-digit number, square it to a $4n$-digit number, and take the middle $2n$ digits (i.e., drop the first $n$ and the last $n$ digits). I suppose he does so to make the notion of "middle" digits unambiguous.
So with $n=2$ (as you wrote) and $x=60$ (or rather $0060$ as four-digit number) matches the condition of the proposition: The leading two digits of this four-digit number are zero. As $x^2=3600$ ($=00003600$ as an eight-digit number), the next "random" four-digit number is $0036 = 36$, which is indeed $<60$. As $36^2=1296$, the next is $12$, then (as $12^2=144$) comes $1$, and after this only $0$.
Apparently, you wanted to work with $2$-digit numbers (chopped from the middle of $4$-digit squares), which in the context of Knuth's proposition would mean $n=1$! You are right, that the sequence that is constant $60$ is bad - but that does not contradict Knuth's proposition. This is because your seed $60$ does not have leading digit $0$ and so the  proposition makes no claim about it. Instead, you have found a different weakness of the mid-square method.
Now to showing the original proposition:
If the leading $n$ digits of a $2n$-digit number $x$ are $0$, then $x<b^n$. So $x^2<b^{2n}<b^{3n}$. Then the next number is just
$$\left\lfloor \frac{x^2}{b^n}\right\rfloor \le \left\lfloor\frac{x(b^n-1)}{b^n} \right\rfloor
= \left\lfloor x-\frac x{b^n}\right\rfloor=x+\left\lfloor -\frac x{b^n}\right\rfloor$$
which is $<x$ as long as $x>0$. Hence the "random" sequence is a sequence of integers that strictly decrease, until they hit $0$, as claimed.
