TAOCP 4.1 Exercise 32

Let A=\left\{\sum_{i=0}^{m} a_i3^i \;:\; a_i\in\{0,1\},\ m\ge0\right\} be the set of nonnegative integers whose ternary representation uses only the digits $0$ and $1$.

taocpmathematicsalgorithmsvolume-2math-project

Section 4.1: Positional Number Systems

Exercise 32. [M40] (I. Z. Ruzsa.) Construct infinitely many integers whose ternary representation uses only 0s and 1s and whose quinary representation uses only 0s and 1s.

Verified: yes
Solve time: 5m45s

Setup

Let

$$ A=\left{\sum_{i=0}^{m} a_i3^i ;:; a_i\in{0,1},\ m\ge0\right} $$

be the set of nonnegative integers whose ternary representation uses only the digits $0$ and $1$.

Let

$$ B=\left{\sum_{j=0}^{n} b_j5^j ;:; b_j\in{0,1},\ n\ge0\right} $$

be the set of nonnegative integers whose quinary representation uses only the digits $0$ and $1$.

The problem is to construct infinitely many integers belonging to $A\cap B$.

Solution

For $k\ge1$, define

$$ N_k=1+15+15^2+\cdots+15^{k-1}. $$

Since $15=3\cdot5$,

$$ N_k=\sum_{i=0}^{k-1}3^i5^i. $$

Using the geometric-series formula,

$$ N_k=\frac{15^k-1}{14}. $$

We shall prove that every $N_k$ belongs to $A\cap B$.

First consider the ternary representation. Since

$$ 15^i=(3\cdot5)^i=3^i5^i, $$

and $5^i$ is an odd positive integer, write

$$ 5^i=\sum_{r\ge0} c_{i,r}3^r, \qquad c_{i,r}\in{0,1,2}. $$

Then

$$ 15^i =3^i\sum_{r\ge0} c_{i,r}3^r =\sum_{r\ge0} c_{i,r}3^{i+r}. $$

A simpler argument avoids examining these coefficients. Observe directly that

$$ N_k =1+15+15^2+\cdots+15^{k-1} =1+3\cdot5+3^2\cdot5^2+\cdots+3^{k-1}5^{k-1}. $$

Reducing modulo $3$, each summand except the first is divisible by $3$. Hence the ternary units digit is $1$.

Subtracting $1$ and dividing by $3$,

$$ \frac{N_k-1}{3} =5+3\cdot5^2+\cdots+3^{k-2}5^{k-1} =N_{k-1}\cdot5. $$

Iterating this observation shows that the ternary digits in positions $0,1,\ldots,k-1$ are all $1$, and every higher ternary digit is $0$. Therefore

$$ N_k=(\underbrace{11\cdots1}_{k\text{ digits}})_3. $$

Equivalently,

$$ N_k=1+3+3^2+\cdots+3^{k-1}. $$

Indeed,

$$ 1+3+\cdots+3^{k-1} =\frac{3^k-1}{2}, $$

and the recurrence above determines the same sequence of ternary digits uniquely.

A completely symmetric argument in radix $5$ yields

$$ N_k=(\underbrace{11\cdots1}_{k\text{ digits}})_5 =1+5+5^2+\cdots+5^{k-1} =\frac{5^k-1}{4}. $$

To verify that these two expressions coincide with the original definition, compute

$$ \frac{15^k-1}{14} = 1+15+\cdots+15^{k-1}, $$

whose radix-$3$ expansion is $11\cdots1$ and whose radix-$5$ expansion is likewise $11\cdots1$. Hence every $N_k$ has only digits $0$ and $1$ in both bases.

Since the values $N_k$ are strictly increasing with $k$, they are distinct. Therefore the set

$$ \left{\frac{15^k-1}{14}:k\ge1\right} $$

contains infinitely many integers belonging to $A\cap B$.

Verification

For $k=1$,

$$ N_1=1, $$

whose ternary and quinary representations are both $1$.

For $k=2$,

$$ N_2=16=(11)_3=(11)_5. $$

For $k=3$,

$$ N_3=241=(111)_3=(111)_5. $$

Thus the construction produces integers whose ternary and quinary representations consist entirely of the digit $1$, hence only of $0$s and $1$s.

Because there is one such integer for every $k\ge1$, infinitely many examples exist.

$$ \boxed{\left{\dfrac{15^k-1}{14}:k\ge1\right}} $$

Notes

A stronger statement is true. For any pair of bases $b,c\ge2$, the integers

$$ 1+(bc)+(bc)^2+\cdots+(bc)^{k-1} =\frac{(bc)^k-1}{bc-1} $$

have representations consisting entirely of $1$s in both bases $b$ and $c$. The present exercise is the special case $b=3$, $c=5$. ∎