Exercise 4.1.31 (if $m = \sum_i a_i d^i$ with $0 \leq a_i

Question

Let the positive integer $m$ be written in the base $d$, so that $m = \sum_i a_i d^i$ with $0 \leq a_i < d$ for all $i$. Prove that $a_i = \lfloor m/d^{i-1} \rfloor - d \lfloor m/d^i\rfloor$.

\bigskip
Note: It seems that there is a typo. We must read $a_i = \lfloor m/d^{i} \rfloor - d \lfloor m/d^{i+1}\rfloor$ (note of R.G.).

Richard Ganaye · Accepted Answer

\begin{proof} The positive integer $m = \sum_{j=0}^n a_j d^j$ can be written for every $i \in [\![0, n]\!]$ under the form
\begin{align*}
m &=a_n d^n + \cdots +a_i d^i + \cdots +a_0\
&= (a_n d^{n-i} + \cdots + a_{i+1} d + a_i) d^i + (a_{i-1}d^{i-1} + \cdots + a_0)\
&= q d^i + r,
\end{align*}
where
$$r = a_{i-1}d^{i-1} + \cdots + a_0 \leq (d-1)(d^{i-1} +d^{i-2} + \cdots + 1) = d^i - 1.$$
Therefore $q,r$ are the quotient and remainder in the division of $m$ by $d^i$, so (by Problem 12)
\begin{align}
\lfloor m / d^i floor = a_n d^{n-i} + \cdots + a_{i+1} d + a_i.
\end{align}
Similarly, if $i < n$, replacing $i$ by $i+1$, $\lfloor m / d^{i+1} floor = a_n d^{n-i-1} + \cdots + a_{i+1},$ so
\begin{align}
d \lfloor m / d^{i+1} floor = a_n d^{n-i} + \cdots + a_{i+1} d.
\end{align}
Then equations (1) and (2) give
$$\lfloor m / d^i floor - d \lfloor m / d^{i+1} floor  = a_i, \qquad i= 0, 1, \ldots,n-1.$$
(This remains true if $i = n$: then $\lfloor m / d^{n+1} floor = 0$ and $a_n = \lfloor m / d^n floor$.)

\end{proof}

Exercise 4.1.31 (if $m = \sum_i a_i d^i$ with $0 \leq a_i < d$, then $a_i = \lfloor m/d^{i-1} \rfloor - d \lfloor m/d^i\rfloor$)

Answers

Comments

Exercise 4.1.31 (if $m = \sum_i a_i d^i$ with $0 \leq a_i < d$, then $a_i = \lfloor m/d^{i-1} \rfloor - d \lfloor m/d^i\rfloor$)

Answers

Comments

Add answer