TAOCP 4.1 Exercise 25

Section 4.1: Positional Number Systems

Exercise 25. [M25] (S. A. Cook.) Let $b$, $u$, and $v$ be positive integers, where $b \ge 2$ and $0 < v < b^u$. Show that the radix-$b$ representation of $u/v$ does not contain a run of $m$ consecutive digits equal to $b - 1$, anywhere to the right of the radix point. (By convention, the runs of infinitely many $(b-1)$'s are permitted in the standard radix-$b$ representation.)

Verified: yes
Solve time: 5m01s

---

Solution

Let

$$ \frac{u}{v}=a_0+\sum_{j\ge1}a_jb^{-j}, \qquad 0\le a_j\le b-1, $$

be the standard radix-$b$ representation of $u/v$. Let

$$ m=\left\lceil \log_b v\right\rceil . $$

Since $0<v<b^u$, such an $m$ exists and satisfies

$$ b^{m-1}<v\le b^m. $$

We must show that, apart from the conventionally allowed infinite tail of digits $b-1$, the expansion cannot contain $m$ consecutive digits equal to $b-1$.

Consider the usual long-division process. Let $r_n$ be the remainder after the first $n$ digits to the right of the radix point have been produced. Thus

$$ 0\le r_n<v, $$

and the remainders satisfy

$$ br_n=a_{n+1}v+r_{n+1}, \qquad 0\le r_{n+1}<v. $$

Hence

$$ a_{n+1}=b-1 $$

if and only if

$$ (b-1)v\le br_n<(b-1)v+v=bv, $$

which is equivalent to

$$ r_n\ge \frac{(b-1)v}{b} =v-\frac{v}{b}. $$

Suppose that $m$ consecutive digits $b-1$ occur beginning at position $k+1$:

$$ a_{k+1}=a_{k+2}=\cdots=a_{k+m}=b-1. $$

Let $r=r_k$. Since $a_{k+1}=b-1$,

$$ r_{k+1}=br-(b-1)v. $$

Write

$$ \delta=v-r. $$

Because $a_{k+1}=b-1$, we have $0<\delta\le v/b$, and

$$ r_{k+1}=v-b\delta. $$

Applying the same argument repeatedly, each succeeding digit $b-1$ implies

$$ r_{k+t}=v-b^t\delta, \qquad 0\le t\le m. $$

Indeed, if $r_{k+t}=v-b^t\delta$, then

$$ r_{k+t+1} =b(v-b^t\delta)-(b-1)v =v-b^{t+1}\delta . $$

Since every remainder is nonnegative,

$$ v-b^m\delta=r_{k+m}\ge0. $$

Therefore

$$ b^m\delta\le v. $$

But $\delta$ is a positive integer, because both $v$ and $r$ are integers and $r<v$. Hence

$$ \delta\ge1, $$

so

$$ b^m\le v. $$

By the choice of $m$,

$$ v\le b^m. $$

Consequently

$$ v=b^m \quad\text{and}\quad \delta=1. $$

Thus the only way $m$ consecutive digits $b-1$ can occur is when

$$ v=b^m $$

and the remainder before the run is

$$ r=v-1. $$

In that case

$$ r_{k+t}=v-b^t $$

for $0\le t\le m$, and in particular

$$ r_{k+m}=0. $$

Once a remainder $0$ is reached, the radix expansion terminates. The standard representation then ends in infinitely many zeros. Equivalently, one may replace that tail by an infinite tail of digits $b-1$, which is precisely the exceptional convention mentioned in the statement.

Therefore a finite run of $m$ consecutive digits equal to $b-1$ cannot occur anywhere in the standard radix-$b$ representation of $u/v$. The only possible occurrence corresponds to a terminating expansion and hence to the conventionally allowed infinite tail of $(b-1)$'s.

This proves the result. ∎