TAOCP 1.1 Exercise 6
By definition, $T_5$ is the average number of times step E1 is performed, taken over all positive integers $m$ when $n=5$.
Exercise 6. [20] What is $T_5$, the average number of times step E1 is performed when $n = 5$?
Verified: yes
Solve time: 47s
By definition, $T_5$ is the average number of times step E1 is performed, taken over all positive integers $m$ when $n=5$. Since the greatest common divisor depends only on the remainder of $m$ modulo $5$, and since step E1 replaces $(m,n)$ by $(5,r)$ where $r$ is the remainder upon dividing $m$ by $5$, the number of performances of E1 depends only on $m \bmod 5$. Thus it suffices to average over the five possible remainders $r \in {0,1,2,3,4}$.
Let $t(m,5)$ denote the number of times E1 is performed.
If $m \equiv 0 \pmod 5$, step E1 produces $r=0$, and step E2 terminates immediately. Hence
$$ t(m,5)=1. $$
If $m \equiv 1 \pmod 5$, the first execution of E1 gives $r=1$. Step E3 sets $m \leftarrow 5$, $n \leftarrow 1$. A second execution of E1 divides $5$ by $1$ and gives remainder $0$, so the algorithm terminates. Hence
$$ t(m,5)=2. $$
If $m \equiv 2 \pmod 5$, the first execution of E1 gives $r=2$. Step E3 yields $(m,n)=(5,2)$. The next execution gives remainder $1$, and the following execution gives remainder $0$. Hence
$$ t(m,5)=3. $$
If $m \equiv 3 \pmod 5$, the first execution gives $r=3$, then $(m,n)=(5,3)$. The next execution gives remainder $2$, then $(m,n)=(3,2)$. The following execution gives remainder $1$, and the next gives remainder $0$. Hence
$$ t(m,5)=4. $$
If $m \equiv 4 \pmod 5$, the first execution gives $r=4$, then $(m,n)=(5,4)$. The subsequent remainders are $1$ and $0$. Hence
$$ t(m,5)=3. $$
Therefore the average number of performances of E1 is
$$ T_5 = \frac{1+2+3+4+3}{5} = \frac{13}{5}. $$
Thus
$$ \boxed{T_5=\frac{13}{5}}. $$