TAOCP 4.1 Exercise 15

**Exercise 4.

taocpmathematicsalgorithmsvolume-2

Section 4.1: Positional Number Systems

Exercise 15. [**] [M24] What are the sets $S = {\sum_{k \ge 0} a_k b^{-k} \mid a_k \text{ an allowable digit}}$, analogous to Fig. 1, for the negative decimal and for the quater-imaginary number systems?

Verified: yes
Solve time: 2m41s

Exercise 4.1.15 [**]

15. [M24] Determine the sets

$$ S = \left{\sum_{k \ge 0} a_k b^{-k} ;\middle|; a_k \text{ an allowable digit}\right} $$

for the negative decimal and the quater-imaginary number systems.

Corrected Solution

We consider each number system separately.

(a) Negative decimal system

Let $b = -10$ and allowable digits $a_k \in {0,1,\dots,9}$. Every number in the system has an expansion

$$ x = \sum_{k\ge0} a_k (-10)^{-k}. $$

Separate the series into even and odd indices:

$$ x = \sum_{j \ge 0} a_{2j} 10^{-2j} - \sum_{j \ge 0} a_{2j+1} 10^{-(2j+1)}. $$

Define

$$ u = \sum_{j\ge0} a_{2j} 10^{-2j}, \quad v = \sum_{j\ge0} a_{2j+1} 10^{-(2j+1)}. $$

Then

$$ x = u - v. $$

The maximal values of $u$ and $v$ occur when all digits take their maximal value $9$:

$$ u_{\max} = \sum_{j\ge0} 9\cdot 10^{-2j} = 9 \sum_{j\ge0} 10^{-2j} = \frac{9}{1-10^{-2}} = \frac{100}{11}, $$

$$ v_{\max} = \sum_{j\ge0} 9 \cdot 10^{-(2j+1)} = 9\cdot 10^{-1} \sum_{j\ge0} 10^{-2j} = \frac{9/10}{1-10^{-2}} = \frac{10}{11}. $$

Similarly, $u_{\min} = v_{\min} = 0$.

Thus the minimal and maximal values of $x = u-v$ are

$$ x_{\min} = 0 - v_{\max} = -\frac{10}{11}, \quad x_{\max} = u_{\max} - 0 = \frac{100}{11}. $$

To show that all intermediate values are attainable, observe the following:

  • Consider the function $f(a_0, a_1, a_2, \dots) = \sum_{j\ge0} a_{2j} 10^{-2j} - \sum_{j\ge0} a_{2j+1} 10^{-(2j+1)}$.
  • For any $x_0$ in $[-10/11, 100/11]$, we can construct a sequence ${a_k}$ iteratively. At step $n$, choose $a_n \in {0,\dots,9}$ so that the partial sum $\sum_{k=0}^n a_k (-10)^{-k}$ approximates $x_0$ to within the maximum possible contribution of the remaining terms.
  • The remaining terms form a series bounded by a geometric series with ratio $10^{-1} < 1$, so it is always possible to pick $a_n$ to keep the running sum within reach of $x_0$.

By induction, this constructs a sequence of allowable digits converging to any $x_0 \in [-10/11, 100/11]$. Hence, every number in the interval is represented.

$$ \boxed{S = \left[-\frac{10}{11},, \frac{100}{11}\right]}. $$

(b) Quater-imaginary system

Let $b = 2i$ and digits $a_k \in {0,1,2,3}$. Every number has the expansion

$$ x = \sum_{k \ge 0} a_k (2i)^{-k}. $$

Separate even and odd powers:

$$ x = \sum_{j\ge0} a_{2j} (2i)^{-2j} + \sum_{j\ge0} a_{2j+1} (2i)^{-(2j+1)}. $$

Since $(2i)^{-2} = -\frac14$, we have

$$ \sum_{j\ge0} a_{2j} (2i)^{-2j} = \sum_{j\ge0} a_{2j} (-1/4)^j, \quad \sum_{j\ge0} a_{2j+1} (2i)^{-(2j+1)} = \frac{1}{2i} \sum_{j\ge0} a_{2j+1} (-1/4)^j. $$

Let

$$ u = \sum_{j\ge0} a_{2j} (-1/4)^j, \quad v = \sum_{j\ge0} a_{2j+1} (-1/4)^j. $$

Then

$$ x = u + \frac{1}{2i} v = u - \frac{i}{2} v. $$

The series $u$ and $v$ are of the same form as a base $-4$ expansion with digits $0,1,2,3$. The maximal and minimal sums are

$$ u_{\min} = v_{\min} = 0, \quad u_{\max} = v_{\max} = \sum_{j\ge0} 3 (-1/4)^j = \frac{3}{1 - (-1/4)} = \frac{3}{5/4} = \frac{12}{5}. $$

The minimal value of $u$ occurs when digits alternate to maximize negative contributions, giving

$$ u_{\min} = -\frac{4}{5}, \quad v_{\min} = -\frac{4}{5}. $$

Thus $u \in [-4/5, 16/5]$ and $v \in [-4/5,16/5]$.

To justify that all points in the rectangle are attainable, we use the same iterative argument as in part (a):

  • For any target complex number $x_0 = x + iy$ in the rectangle

$$ x \in [-4/5, 16/5], \quad y \in [-8/5, 2/5], $$

we construct the sequences ${a_{2j}}$ and ${a_{2j+1}}$ independently, choosing each digit to approximate $u$ and $v$ respectively within the remaining tail of the geometric series.

  • Because the geometric series is summable and the maximal contribution of remaining terms decreases exponentially, each step allows a choice of $a_k$ to remain on track to reach the target.

Hence, all points in the rectangle in the complex plane are represented.

$$ \boxed{S = \left{ x + i y ;\middle|; -\frac{4}{5} \le x \le \frac{16}{5},\ -\frac{8}{5} \le y \le \frac{2}{5} \right}}. $$

Answer (Final Form)

$$ \begin{aligned} \text{Negative decimal:} & \quad S = \left[-\frac{10}{11}, \frac{100}{11}\right],\ \text{Quater-imaginary:} & \quad S = \left{ x + i y ;\middle|; -\frac{4}{5} \le x \le \frac{16}{5},\ -\frac{8}{5} \le y \le \frac{2}{5} \right}. \end{aligned} $$

These sets are exactly the intervals (or rectangle) of representable numbers using the respective number systems. All points in the intervals are attainable by appropriate infinite digit sequences.