TAOCP 3.1 Exercise 3
In the middle-square method with a fixed length of $10$ digits, we begin with x=1010101010.
Exercise 3. [10] What number follows 1010101010 in the middle-square method?
Verified: yes
Solve time: 3m58s
In the middle-square method with a fixed length of $10$ digits, we begin with
$$ x=1010101010. $$
Step E1 requires us to compute $x^2$. Write
$$ x=10(1+10^2+10^4+10^6+10^8). $$
Let
$$ S=1+10^2+10^4+10^6+10^8. $$
Then
$$ x^2=10^2S^2. $$
To compute $S^2$, note that the exponents occurring in $S$ are
$$ 0,2,4,6,8. $$
The coefficient of $10^{2k}$ in $S^2$ is the number of ordered pairs $(i,j)$ from this set with $i+j=2k$. Hence the coefficients are
$$ 1,2,3,4,5,4,3,2,1, $$
so
$$ S^2 =1+2\cdot10^2+3\cdot10^4+4\cdot10^6+5\cdot10^8 +4\cdot10^{10}+3\cdot10^{12}+2\cdot10^{14}+10^{16}. $$
Therefore
$$ \begin{aligned} x^2 &=10^2S^2\ &=10^2+2\cdot10^4+3\cdot10^6+4\cdot10^8+5\cdot10^{10}\ &\qquad +4\cdot10^{12}+3\cdot10^{14}+2\cdot10^{16}+10^{18}. \end{aligned} $$
Since every coefficient is at most $5$, no carrying occurs. Thus
$$ x^2 = 1020304050403020100. $$
This is a $19$-digit number:
$$ 1,0,2,0,3,0,4,0,5,0,4,0,3,0,2,0,1,0,0. $$
For a $19$-digit number, the middle $10$ digits are positions $6$ through $15$ from the left. Hence
$$ 1,0,2,0,3, \boxed{0,4,0,5,0,4,0,3,0,2}, 0,1,0,0. $$
Therefore the number that follows $1010101010$ in the middle-square method is
$$ \boxed{0405040302}. $$
Equivalently, as a numerical value, it is $405040302$. ∎