TAOCP 1.1 Exercise 7
For a fixed positive integer $m$, define $U_m$ to be the average number of executions of step E1 in Algorithm E when the second argument $n$ ranges over all positive integers.
Exercise 7. ▶ [M21] Suppose that $m$ is known and $n$ is allowed to range over all positive integers; let $U_m$ be the average number of times that step E1 is executed in Algorithm E. Show that $U_m$ is well defined. Is $U_m$ in any way related to $T_m$?
Verified: yes
Solve time: 48s
For a fixed positive integer $m$, define $U_m$ to be the average number of executions of step E1 in Algorithm E when the second argument $n$ ranges over all positive integers.
Since there are infinitely many values of $n$, the meaning of "average" must be made precise. Let
$$ U_m(N)=\frac1N\sum_{n=1}^{N}E(m,n), $$
where $E(m,n)$ denotes the number of times step E1 is executed when Algorithm E is applied to the pair $(m,n)$. Then $U_m$ is well defined if the limit
$$ U_m=\lim_{N\to\infty}U_m(N) $$
exists.
To prove existence, first determine the behavior of $E(m,n)$ when $n>m$.
If $n>m$, the first execution of step E1 divides $m$ by $n$, producing remainder $r=m$. Step E3 then sets
$$ m\leftarrow n,\qquad n\leftarrow m, $$
so the effect is to interchange the two arguments. After this interchange, the algorithm proceeds exactly as it would have proceeded from the initial pair $(n,m)$. Therefore
$$ E(m,n)=1+E(n,m), \qquad n>m. $$
For fixed $m$, the quantity $E(n,m)$ depends only on the remainder of $n$ modulo $m$, because step E1 computes the remainder of $n$ upon division by $m$. Hence
$$ E(n,m)=E(r,m) $$
whenever $n\equiv r\pmod m$ and $0\le r<m$.
Define
$$ c_r=E(r,m)\qquad (1\le r<m), $$
and observe that
$$ E(m,m)=1, $$
since the first division gives remainder $0$.
For $n>m$ we therefore have
$$ E(m,n)=1+c_r, $$
where $r$ is the residue of $n$ modulo $m$. Thus the values of $E(m,n)$ for $n>m$ are periodic with period $m$.
Let
$$ A=\frac1m\left(E(m,m)+\sum_{r=1}^{m-1}(1+c_r)\right). $$
Among the integers $1\le n\le N$, each residue class modulo $m$ occurs with asymptotic frequency $1/m$. Since $E(m,n)$ is periodic for all $n\ge m$, the Cesàro average $U_m(N)$ tends to $A$. Hence the limit exists, and $U_m$ is well defined.
It remains to relate $U_m$ to $T_m$. By definition, $T_m$ is the average value of $E(m,n)$ for $1\le n\le m$:
$$ T_m=\frac1m\left(E(m,m)+\sum_{r=1}^{m-1}E(m,r)\right). $$
For $1\le r<m$, the relation established above gives
$$ E(m,r)=1+E(r,m)=1+c_r. $$
Substituting into the formula for $T_m$,
$$ T_m =\frac1m\left(E(m,m)+\sum_{r=1}^{m-1}(1+c_r)\right) =A. $$
But $A$ is exactly the limiting average defining $U_m$. Therefore
$$ U_m=T_m. $$
Thus $U_m$ is well defined, and it is equal to $T_m$.
$$ \boxed{U_m=T_m} $$
This completes the proof.
∎