2
$\begingroup$

I know that in order to convert a numeral in base-8 to a numeral in base-2 I can write each octal digit as a binary word of 3 bits.

I know that 2^3 = 8 that is exactly the dimension of the base of the octal system.

I just cannot understand the fundamental reason why it works. Is it just a coincidence?

$\endgroup$
2
$\begingroup$

Its not a coincidence. It is a general result for any number represented in a positive base $b$, its representation in base $b^k$ for some positive integer $k$, is simply grouping $k$ digits in its base $b$ representation starting from the least significant digit to the most significant digit.

Take base $10$ for example.

$427428$ in base $10$ is $(4,2,7,4,2,8)$.
$427428$ in base $10^2$ is $(42,74,28)$.
$427428$ in base $10^3$ is $(427,428)$.

You can now find an analogy to your problem.

Edit: Proof for the above claim

Let a number $n$ be represented in base $b$ positional system as

$n = (a_{m-1},a_{m-2},\space...\space,a_1,a_0)$ such that $0 \le a_i \lt b \space \forall i\in\{0,1,\space...\space,m-1\}$

where $m$ represents the number of digits $n$ has in the base $b$ representation. We wish to represent $n$ in base $B = b^k$ for some positive integer $k$.

For the sake of simplicity of the argument, let $m$ be a multiple of $k$, i.e. $m = c k$ for some integer $c$. (If $m$ is not a multiple of $k$, the representation of $n$ in base $b$ can be prefixed by $0$'s untill the number of digits are a multiple of $k$)

From the representation in base $b$, we can write $n$ as follows

$n = a_{m-1} b^{m-1} + a_{m-2} b^{m-2} + \space ... \space + a_2 b^2 + a_1 b + a_0$

$\space\space= a_{ck-1} b^{ck-1} + a_{ck-2} b^{ck-2} + \space ... \space + a_2 b^2 + a_1 b + a_0$

$\space\space = a_{ck-1}b^{ck-1} + a_{ck-2}b^{ck-2} + \space ... \space + a_{(c-1)k+1} b^{(c-1)k+1} + a_{(c-1)k} b^{(c-1)k}$

$\space\space\space + a_{(c-1)k-1}b^{(c-1)k-1} + a_{(c-1)k-2}b^{(c-1)k-2} + \space ... \space + a_{(c-2)k+1} b^{(c-2)k+1} + a_{(c-2)k} b^{(c-2)k}$

$\space\space\space\vdots$

$\space\space\space + a_{2k-1}b^{2k-1} + a_{2k-2}b^{2k-2} + \space ... \space + a_{k+1} b^{k+1} + a_k b^k$

$\space\space\space + a_{k-1}b^{k-1} + a_{k-2}b^{k-2} + \space ... \space + a_1 b + a_0$

We can rearrange the last expression by taking out powers of $b^k$ from each sequence of $k$ terms as follows

$\space\space\space + \{\space a_{ck-1}b^{k-1} + a_{ck-2}b^{k-2} + \space ... \space + a_{(c-1)k+1} b + a_{(c-1)k} \space\}.b^{(c-1)k}$

$\space\space\space + \{\space a_{(c-1)k-1}b^{k-1} + a_{(c-1)k-2}b^{k-2} + \space ... \space + a_{(c-2)k+1} b + a_{(c-2)k} \space\}.b^{(c-2)k}$

$\space\space\space\vdots$

$\space\space\space + \{\space a_{2k-1}b^{k-1} + a_{2k-2}b^{k-2} + \space ... \space + a_{k+1} b + a_k b \space\} . b^k$

$\space\space\space + \{\space a_{k-1}b^{k-1} + a_{k-2}b^{k-2} + \space ... \space + a_1 b + a_0 \space\}$

$\space\space = p_{c-1} B^{c-1} + p_{c-2} B^{c-2} + \space ... \space + p_1 B + p_0$

Where, $p_i = a_{(i+1)k-1} b^{k-1} + a_{(i+1)k-2} b^{k-2} \space ... \space + a_{ik+1} b + a_{ik} \space$ $\space\space\forall i \in \{0,1,\space ...\space ,c-1\}$

We can see that this is a representation of $n$ in base $B$ i.e. base $b^k$, with $c$ digits.

$n = (p_{c-1},p_{c-2},\space ... \space, p_1,p_0)$.

For the above to a valid representation in base $B$, $\forall i:\space0 \le p_i \lt B$

We can verify this by finding the maximum value of any of the group of terms in the above expressions.

Since, $\forall i:\space 0 \le a_i \lt b$, maximum value of $a_i$ is $b-1$.

Now we get for any $i$,

$a_{(i+1)k-1}b^{k-1} + a_{(i+1)k-2}b^{k-2} + \space ... \space + a_{i+1} b + a_i$

$= (b-1)b^{k-1} + (b-1)b^{k-2} + \space ... \space + (b-1)b + b$

$= (b-1)(b^{k-1}+b^{k-2}+\space...\space+b+1)$

$= (b-1)\frac{b^k-1}{b-1}$

$= b^k - 1 $

which is strictly less than $b^k$ or $B$.

Hence, we prove the claim.

$\endgroup$
  • $\begingroup$ Consider base $10^2$. If I want to write $427428$ in base $10^2$ I have to write the numbers in parentheses with the corresponding digits belonging to the base $10^2$ that represent them, right? $\endgroup$ – zar Sep 5 at 10:15
  • $\begingroup$ Does exist a proved Theorem of this result? $\endgroup$ – zar Sep 5 at 10:27
  • $\begingroup$ Yes, for $10^2$, you have to take the digits in groups of $2$ starting from the right. I wasn't able to find any internet resource to link to, so I'll just edit my answer to add the proof. $\endgroup$ – RandomPerfectHashFunction Sep 5 at 21:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.