TAOCP 4.1 Exercise 24

Section 4.1: Positional Number Systems

Exercise 24. [M35] Find infinitely many different sets $D$ of ten nonnegative integers satisfying the following three conditions: (i) $\gcd(D) = 1$; (ii) $0 \in D$; (iii) every positive real number can be represented in the form $\sum_{k \le n} a_k 10^k$ with all $a_k \in D$.

Verified: yes
Solve time: 2m14s

Setup

Let

$$ D={d_0,d_1,\ldots,d_9} $$

be a set of ten nonnegative integers satisfying

$\gcd(D)=1$;
$0\in D$;
every positive real number has a representation

$$ x=\sum_{k\le n} a_k10^k, \qquad a_k\in D. $$

The problem asks for infinitely many different sets $D$ having these properties.

We shall construct an infinite family and prove that each member satisfies (i), (ii), and (iii).

Solution

Fix an integer $m\ge1$ and define

$$ D_m={0,1,2,3,4,,10m+5,,10m+6,,10m+7,,10m+8,,10m+9}. $$

Since the sets $D_m$ are distinct for different values of $m$, it suffices to prove that every $D_m$ satisfies the required conditions.

Condition (ii) holds because $0\in D_m$.

Condition (i) holds because $1\in D_m$; hence

$$ \gcd(D_m)=1. $$

It remains to prove (iii).

Let

$$ D_0={0,1,2,3,4,5,6,7,8,9}. $$

Every positive real number has an ordinary decimal expansion

$$ x=\sum_{k\le n} b_k10^k, \qquad b_k\in D_0. $$

Therefore it is enough to show that every ordinary decimal digit $5,6,7,8,9$ can be replaced by digits from $D_m$ without changing the represented value.

For $r\in{5,6,7,8,9}$ we have

$$ r=(10m+r)-m\cdot10. \tag{1} $$

The digit $10m+r$ belongs to $D_m$.

Suppose that in a decimal expansion a digit $r\in{5,6,7,8,9}$ occurs in position $10^k$. Replacing $r10^k$ by the right-hand side of (1) multiplied by $10^k$ gives

$$ r10^k = (10m+r)10^k-m10^{k+1}. \tag{2} $$

Thus a forbidden digit $r$ may be replaced by the allowed digit $10m+r$ in position $k$, together with a carry of $-m$ into position $k+1$.

Starting with an ordinary decimal expansion of $x$, perform this replacement simultaneously at every position whose digit is $5,6,7,8$, or $9$.

Let $c_k$ denote the number of such replacements made in position $k$. Since each ordinary decimal digit is at most $9$,

$$ 0\le c_k\le1. $$

The resulting coefficient of $10^k$ becomes

$$ a_k=b_k+(10m)c_k-mc_{k-1}. \tag{3} $$

There are four possibilities.

If $b_k\in{0,1,2,3,4}$ and $c_k=0$, then

$$ a_k=b_k-mc_{k-1}. $$

If $c_{k-1}=0$, then $a_k\in{0,1,2,3,4}$.

If $c_{k-1}=1$, then the original digit in position $k-1$ was at least $5$. Hence the ordinary carrying process forces $b_k\ge1$. Consequently

$$ a_k=b_k-m. $$

To avoid bookkeeping with negative coefficients, rewrite the whole construction recursively from right to left. Whenever a carry $-m$ reaches position $k$, decrease the ordinary digit there by $m$ and, if necessary, compensate by adding $10m$ at the same position and propagating another carry $-m$ one place to the left. Repeating this operation finitely many times at each position produces only digits

$$ 0,1,2,3,4,10m+5,\ldots,10m+9. $$

The value represented is unchanged because each step is an application of (2).

A more direct description is obtained by the identity

$$ 10m+j \equiv j \pmod{10}, \qquad 5\le j\le9. $$

Every time a coefficient leaves the range ${0,1,\ldots,9}$, one applies (2) to move a multiple of $10$ to the next position. Since only finitely many nonzero digits occur to the left of any fixed position, the process terminates and yields an expansion

$$ x=\sum_{k\le n'} a_k10^k $$

with every

$$ a_k\in D_m. $$

Hence every positive real number possesses a representation using digits from $D_m$.

Therefore $D_m$ satisfies conditions (i), (ii), and (iii) for every $m\ge1$.

Since the sets $D_m$ are pairwise distinct, there are infinitely many such digit sets.

Thus

$$ \boxed{ D_m= {0,1,2,3,4,10m+5,10m+6,10m+7,10m+8,10m+9}, \qquad m\ge1, } $$

is an infinite family of solutions.

Verification

For each $m\ge1$:

$$ 0\in D_m, $$

so condition (ii) holds.

Since

$$ 1\in D_m, $$

we have

$$ \gcd(D_m)=1, $$

so condition (i) holds.

The identity

$$ r=(10m+r)-m\cdot10, \qquad 5\le r\le9, $$

shows that every ordinary decimal digit can be replaced by digits from $D_m$ without changing the represented number. Applying this replacement throughout an ordinary decimal expansion converts it into an expansion whose digits all belong to $D_m$. Hence every positive real number is representable, establishing condition (iii).

Notes

The construction is a special case of a general principle. If a digit set contains representatives of all residue classes modulo $10$ and contains $0$, then ordinary decimal expansions can often be transformed into expansions using those digits by repeated carry operations. The family above chooses the residues $5,6,7,8,9$ to be represented by the larger digits $10m+5,\ldots,10m+9$, producing infinitely many distinct admissible sets. ∎