TAOCP 4.1 Exercise 10

Section 4.1: Positional Number Systems

Exercise 10. [**] [M22] Generalize Eq. (5) to mixed-radix notation as in (9).

Verified: yes
Solve time: 3m48s

Exercise 4.1.10 [**]

10. [M22] Generalize Eq. (5) to mixed-radix notation as in (9).

Solution.

Let the mixed radices be $r_1,r_2,r_3,\ldots$, with $r_j\ge2$, and define

$$ R_j=r_1r_2\cdots r_j \qquad (j\ge1). $$

In the notation of (9),

$$ (.a_1a_2a_3\ldots) = \sum_{j\ge1}\frac{a_j}{R_j}, \qquad 0\le a_j<r_j. $$

Equation (5) for ordinary radix $r$ states that

$$ (.a_1a_2\ldots) = \sum_{j\ge1}\frac{a_j}{r^j}. $$

The corresponding formula in mixed-radix notation is therefore simply

$$ \boxed{ (.a_1a_2a_3\ldots) = \sum_{j\ge1}\frac{a_j}{r_1r_2\cdots r_j} }. $$

This is the desired generalization.

If the expansion terminates after $n$ digits, the formula becomes

$$ (.a_1a_2\ldots a_n) = \sum_{j=1}^n \frac{a_j}{r_1r_2\cdots r_j}. $$

Equivalently, multiplying by $R_n$ gives

$$ R_n(.a_1a_2\ldots a_n) = a_1r_2r_3\cdots r_n +a_2r_3r_4\cdots r_n +\cdots +a_{n-1}r_n +a_n, $$

hence

$$ \boxed{ (.a_1a_2\ldots a_n) = \frac{ a_1r_2r_3\cdots r_n +a_2r_3r_4\cdots r_n +\cdots +a_{n-1}r_n +a_n }{ r_1r_2\cdots r_n }. } $$

This is exactly analogous to Eq. (5), with the powers $r^j$ replaced by the positional products $r_1r_2\cdots r_j$.

No geometric-series argument is available in general, because the positional weights do not scale by a constant factor unless the radix sequence itself is periodic.