6
$\begingroup$

Why can we convert a base $9$ number to a base $3$ number by simply converting each base $9$ digit into two base $3$ digits ?

For example $813_9$ can be converted directly to base $3$ by noting

\begin{array} \space 8_9&=22_3 \\ \space 1_9 &=01_3 \\ \space 3_9 &=10_3 \\ \end{array}

Putting the base digits together ,we get $$813_9=220110_3$$

I know it has to do with the fact that $9=3^2$ but I am not able to understand this all by this simple fact...

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ This is actually useful (but not with $9$ and $3$). We can very cheaply go back and forth between hexadecimal (base $16$) and binary. $\endgroup$ – André Nicolas Jan 26 '16 at 8:30
  • $\begingroup$ This also applies to converting between: binary, octal, hexadecimal systems $\endgroup$ – Max Payne Jan 26 '16 at 8:31
3
$\begingroup$

Consider $N$ in base 3. For simplicity, we can assume that $N_3$ has an even number of digits: if it doesn't, just tack on a leftmost $0$. So let: $$N_3 = t_{2n+1} t_{2n}\dotsc t_{2k+1} t_{2k} \dotsc t_1 t_0. $$ What this positional notation really means is that: $$ N = \sum_{i = 0}^{2n+1} t_i 3^i, $$ which we can rewrite as: $$\begin{align} N &= \sum_{k = 0}^{n} (t_{2k+1} 3^{2k+1} + t_{2k} 3^{2k}) \\ &= \sum_{k = 0}^{n} (3 t_{2k+1} + t_{2k}) 3^{2k} \\ &= \sum_{k = 0}^{n} (3 t_{2k+1} + t_{2k}) 9^{k}. \\ \end{align}$$

But now, note that for each $k$, $3 t_{2k+1} + t_{2k}$ is precisely the base-9 digit corresponding to the consecutive pair of base-3 digits $t_{2k+1} t_{2k}$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Altough I've already accepted an answer,I thought to let you know that this answer has been so insightful.Thanks for your time ! $\endgroup$ – Mr. Y Jan 26 '16 at 9:18
  • $\begingroup$ How nice — thank you:) and you're welcome. $\endgroup$ – BrianO Jan 26 '16 at 9:24
  • 2
    $\begingroup$ That is the real good prove $\endgroup$ – JnxF Jan 26 '16 at 9:57
  • $\begingroup$ Oh my - thanks doubly. $\endgroup$ – BrianO Jan 26 '16 at 10:05
  • $\begingroup$ yes this is the proof. My answer is just a visual. +1 $\endgroup$ – Max Payne Jan 26 '16 at 10:16
4
$\begingroup$

This has more to do with place value.

Consider the image:

enter image description here

The key is the fact that $3^2 = 9$

  • All the value below $3^2$ ($3^0 $ and $ 3^1 $) has to be accomodated in $9^0$

    that is

  • all the values in $9^0$ have to be accommodated in the two places below $3^2$ ($3^0 $ and $ 3^1 $)

Similarly for any other places.

  • This rule also applies to conversion between binary and octal, or binary and hexadecimal, or conversion between any base $k$ and base $k^n$

In general, for conversion of a number $N$ in any base $k$ to base $k^n$, each digit of $N_{k^n}$ get converted to n digits of $N_k$

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks for the answer .One question : in general if we have that some number $c$ (I am considering everything in base $10$) such that $c=b^n$ does this mean that I can convert the number $c$ in base $b$ by simple converting each base $10$ digit of $c$ into $n$ base $b$ digits ?Or is this something that works only for these special cases ? $\endgroup$ – Mr. Y Jan 26 '16 at 8:56
  • 1
    $\begingroup$ @Mr.Y, yes, you can. An even stronger statement would be: given $a^n=b^m$, we could convert a base $a^n$ number, say, $k$, to base $b^m$, by converting every $n$ digits of $k$ (base $a^n$) to $m$ digits base $b^m$. $\endgroup$ – vrugtehagel Jan 26 '16 at 9:02
2
$\begingroup$

I'm not sure whether you're asking for a proof, or some intuition. The proof is fairly mechanical, so I'll explain why you might expect this to be true.

Putting your information theory hat on, two base 3 digits carry exactly as much information as one base 9 digit. That is, suppose you know I'm going to pass you two digits, each from 0,1 and 2. Then you know there are $3 \cdot 3 =9$ possibilities for what information I could pass.

On the other hand, if I passed you a single digit from 0,1,...,8, then there are again 9 possibilities.

Continuing in this fashion, $n$ digits of base 9 pass as much information as $2n$ digits of base 3.

This isn't exactly a proof yet. You'd need to prove that you don't skip any values. Perhaps doing the computation you describe can never return the value $102_3$. Thankfully it can. But you'd need to think about why this will always work.

|cite|improve this answer
$\endgroup$
2
$\begingroup$

Let's look at what you base $9$ number actually means. $$813_9=8\cdot 9^2+1\cdot 9^1+3\cdot 9^0$$ If we wish to write this as powers of $3$ with coefficients between $0$ and $2$, we can simply do \begin{align} 3\cdot 9^0&=1\cdot 3^1+0\cdot 3^0\\ 1\cdot 9^1&=0\cdot 3^3+1\cdot 3^2\\ 8\cdot 9^2&=2\cdot 3^5+2\cdot 3^4\\ \end{align}

Why can we do this?

Why can we write $$a_n\cdot 9^n=b_{2n+1}\cdot 3^{2n+1}+b_{2n}\cdot3^{2n}$$ First note that $9^n3^2n$, so when dividing the equation by that, we get $$\frac{a_n\cdot 9^n}{3^{2n}}=a_n=3b_{2n+1}+b_{2n}=\frac{b_{2n+1}\cdot 3^{2n+1}+b_{2n}\cdot3^{2n}}{3^2n}$$ So actually, the problem comes down to writing a number $0\leq a_n<9$ as $3b_{2n+1}+b_{2n}$, where $0\leq b_{2n},b{2n+1}<3$. This is obviously possible.

Why does this work for binary and hexadecimal?

Actually, the answer is fairly similar. The problem can be reduced equivalently, resulting in the equation $$a_n=8a_{4n+3}+4a_{4n+2}+2a_{4n+1}+a_{4n}$$ Where $0\leq a_n<16$ and $0\leq a_{2n+3},a_{2n+2},a_{2n+1},a_{2n}<2$. The solvability of this equation is in my opinion a little less obvious, but still quite understandable; But, for the sake of a more thourough understanding, we could look at hexadecimal-octagonal conversion. This comes down to the easy equation $a_n=2b_{2n+1}+b_{2n}$, where $0\leq a_n<16$ and $0\leq b_{2n+1},b_{2n}<8$. This is cleary solvable. Doing this for octagonal-base 4 conversion and base 4-binary conversion shows with a recurrance-like approach that this indeed works for hexadecimal-binary conversion.

Hope this helped!

|cite|improve this answer
$\endgroup$
2
$\begingroup$

Hint:

$$\color{blue}1\cdot3^5+\color{blue}0\cdot3^4+\color{green}2\cdot3^3+\color{green}2\cdot3^2+\color{red}0\cdot3^1+\color{red}1\cdot3^0 =(\color{blue}1\cdot3^1+\color{blue}0)3^4+(\color{green}2\cdot3^1+\color{green}2)3^2+(\color{red}0\cdot3^1+\color{red}1)3^0\\ =\color{blue}3\cdot9^2+\color{green}8\cdot9^1+\color{red}1\cdot9^0$$

$$\color{blue}{10}\color{green}{22}\color{red}{01}_3=[\color{blue}{10_3}|\color{green}{22_3}|\color{red}{01_3}]_9=\color{blue}3\color{green}8\color{red}1_9$$

|cite|improve this answer
$\endgroup$

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.