TAOCP 4.1 Exercise 19

Assume that every integer in the interval l\le m\le u, \qquad l=-\frac{\max D}{b-1}, \qquad

taocpmathematicsalgorithmsvolume-2

Section 4.1: Positional Number Systems

Exercise 19. ▶ [**] [23] (David W. Matula.) Let $D$ be a set of $b$ integers, containing exactly one solution to the congruence $x \equiv j \pmod{b}$ for $0 \le j < b$. Prove that all integers $m$ (positive, negative, or zero) can be represented in the form $m = (a_n \ldots a_1 a_0)_b$, where all the $a_j$ are in $D$, if and only if all integers in the range $l \le m \le u$ can be so represented,

where $l = -\max{a \mid a \in D}/(b-1)$ and $u = \min{a \mid a \in D}/(b-1)$. For example, $D = {-1, 0, \ldots, b-2}$ satisfies the conditions for all $b \ge 2$. [Hint: Design an algorithm that constructs a suitable representation.]

Verified: yes
Solve time: 3m28s

Assume that every integer in the interval

$$ l\le m\le u, \qquad l=-\frac{\max D}{b-1}, \qquad u=-\frac{\min D}{b-1}, $$

has a representation with digits in $D$. We must prove that every integer has such a representation.

Let

$$ M=\max D,\qquad m_0=\min D. $$

Since $D$ contains exactly one representative of each residue class modulo $b$, for every integer $t$ there is a unique digit $a\in D$ such that

$$ a\equiv t \pmod b. $$

Define the following recursive procedure.

Given $n_0=m$, choose $a_0\in D$ with $a_0\equiv n_0\pmod b$, and set

$$ n_1=\frac{n_0-a_0}{b}. $$

Inductively, having defined $n_k$, choose $a_k\in D$ with

$$ a_k\equiv n_k\pmod b, $$

and set

$$ n_{k+1}=\frac{n_k-a_k}{b}. $$

Then

$$ n_k=b,n_{k+1}+a_k. $$

The recursion is always well defined because $n_k-a_k$ is divisible by $b$.

The essential point is to prove that the sequence $n_k$ eventually enters the interval $[l,u]$.

First suppose that $n_k>u$. Since $a_k\ge m_0$,

$$ n_{k+1} =\frac{n_k-a_k}{b} \le \frac{n_k-m_0}{b}. $$

Because $n_k>u=-m_0/(b-1)$,

$$ (b-1)n_k>-m_0, $$

hence

$$ n_k>\frac{n_k-m_0}{b}. $$

Therefore

$$ n_{k+1}<n_k. $$

Since $n_{k+1}$ is an integer, we actually have

$$ n_{k+1}\le n_k-1. $$

Thus, whenever $n_k>u$, the sequence decreases by at least $1$.

Similarly, suppose that $n_k<l$. Since $a_k\le M$,

$$ n_{k+1} =\frac{n_k-a_k}{b} \ge \frac{n_k-M}{b}. $$

Because $n_k<l=-M/(b-1)$,

$$ (b-1)n_k<-M, $$

hence

$$ n_k<\frac{n_k-M}{b}. $$

Therefore

$$ n_{k+1}>n_k. $$

Since both are integers,

$$ n_{k+1}\ge n_k+1. $$

Thus, whenever $n_k<l$, the sequence increases by at least $1$.

Consequently:

  • if $n_0>u$, the sequence $n_k$ is strictly decreasing until it first reaches a value $\le u$;
  • if $n_0<l$, the sequence $n_k$ is strictly increasing until it first reaches a value $\ge l$.

It remains to show that the sequence cannot jump across the whole interval $[l,u]$.

If $n_k>u$, then

$$ n_{k+1} =\frac{n_k-a_k}{b} \ge \frac{u-M}{b}. $$

Using $u=-m_0/(b-1)$,

$$ \frac{u-M}{b} = \frac{-m_0-(b-1)M}{b(b-1)} \ge -\frac{M}{b-1} =l, $$

because $m_0\le M$.

Hence

$$ n_k>u \implies n_{k+1}\ge l. $$

Likewise, if $n_k<l$,

$$ n_{k+1} =\frac{n_k-a_k}{b} \le \frac{l-m_0}{b} = \frac{-M-(b-1)m_0}{b(b-1)} \le -\frac{m_0}{b-1} =u, $$

again because $m_0\le M$. Thus

$$ n_k<l \implies n_{k+1}\le u. $$

Therefore a term outside $[l,u]$ cannot jump from above $u$ to below $l$, nor from below $l$ to above $u$.

Starting from any integer $m=n_0$, repeated application of the recursion moves the sequence monotonically toward the interval $[l,u]$, and because the values change by at least $1$ at each step while outside the interval, there exists some $N$ such that

$$ l\le n_N\le u. $$

By hypothesis, $n_N$ has a representation

$$ n_N=(a_ta_{t-1}\cdots a_N)_b $$

with all digits in $D$.

Using

$$ n_k=b,n_{k+1}+a_k \qquad (0\le k<N), $$

and substituting successively, we obtain

$$ m=n_0 =(a_ta_{t-1}\cdots a_Na_{N-1}\cdots a_1a_0)_b. $$

Hence every integer $m$ has a finite representation with digits in $D$.

This proves the implication

$$ \bigl(\forall,m\in[l,u],\ m\ \text{representable}\bigr) \Longrightarrow \bigl(\forall,m\in\mathbb Z,\ m\ \text{representable}\bigr). $$

The converse is immediate: If every integer is representable, then certainly every integer in the subset $[l,u]$ is representable.

Therefore all integers can be represented in the form $(a_n\cdots a_1a_0)_b$ with digits from $D$ if and only if all integers in the range

$$ -\frac{\max D}{b-1} \le m\le -\frac{\min D}{b-1} $$

can be so represented. ∎