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.

| cite | improve this answer | |
$\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 '19 at 10:15
  • $\begingroup$ Does exist a proved Theorem of this result? $\endgroup$ – zar Sep 5 '19 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 '19 at 21:01
  • 1
    $\begingroup$ Zar: That’s because we don’t have symbols for 100 “digits” from 00 to 99. It’s entirely possible that some alien centipedes would find counting in base 100 quite natural, and that they would have these 100 symbols in their writing system. $\endgroup$ – gnasher729 Mar 21 at 8:05

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.