Converting from base $2$ to base 3

4.3k Views Asked by At

Transform the binary expansion $y = 0.110110110\ldots$ into a ternary expansion.

We are given that $y = 0.110110110\ldots_2$ and thus $1000_2y = 110_2+y \implies y = \frac{6}{7}$. Then we see that $\frac{6}{7}=0.857142\ldots$. How do I convert this to base $3$?

3

There are 3 best solutions below

3
On

Notice that this is $0.\overline{110}$, so it corresponds to $\frac{110_2}{1000_2-1}=\frac 6 7$.

This is how repeating decimals in different bases work: The repeating part can be written as the part that repeats over the difference between the power of the base and $1$.

We need to find where we can do this for $\frac 6 7$ in base $3$. We need to find: $$\frac 6 7=\frac{a}{3^b-1}$$ We can do this by guessing and checking values of $b$ and seeing if $a$ is an integer. After guessing $b=1,2,3,4,5$, we get non-integer $a$s, but $b=6$ yields $a=624$, so we have: $$\frac 6 7=\frac{624}{3^6-1}=\frac{212010_3}{1000000_3-1}$$ Thus, the answer is $0.\overline{212010}_3$.


As @BarryCipra, we can solve this without guessing using modular arithmetic:

We want $a=6\frac{3^b-1}{7}$ to be an integer. Leave $6$ out of this since there's no way it's cancelling with the $7$. Thus, $3^b-1$ needs to be a multiple of $7$, so we have: $$3^b-1 \equiv 0 \pmod 7$$ Add $1$ to both sides: $$3^b \equiv 1 \pmod 7$$ Now apply Euler's theorem to get $b=\phi(7)$ as a solution. In this case, $\phi(7)$ is the smallest possible power because $3$ is a primitive root $\pmod 7$.

Note that $\phi(d)$ won't always be the smallest power. For example, in the case of $$\frac 1 8=\frac{a}{3^b-1}$$ If we use $b=\phi(8)=4$, we get $a=10=101_3$ and thus: $$\frac 1 8=0.\overline{0101}_3$$ However, this can be simplified to: $$\frac 1 8=0.\overline{01}_3$$ meaning that $b=2$ was the actual smallest power. However, it still works out because we still find the pattern using $\phi(d)$ and we can simplify the decimal once we find the repeating pattern.

0
On

You can do long division in base $3$ now that you have the decimal representation: $20_3 \div 21_3$. Once you find a repeating remainder, you've finished the pattern.

0
On

I guess forget my comment. If you know the answer is $\frac{6}{7}_{10}$ (that is $\frac{6}{7}$ in base 10), then you can just start finding the base $3$ representation. I would suggest looking at my answer to Algorithm for creating binary rational numbers. I actually discuss base-3 specifically at the bottom of my answer.

When you have a number less than $1$, you simply start multiplying by $3$. If you have an integer greater than $1$, you start dividing by $3$. If you have a mixed number (integer part with a part less than $1$) then you handle the integer and fractional part separately (then every case becomes one of the two above cases).

So start:

$$ 3\cdot \frac{6}{7} = \frac{18}{7} = 2+\frac{4}{7} $$

Your first digit is $2$, that is $0.2..._3$. Now you repeat (and keep going until you find a repetition):

$$ 3\cdot \frac{4}{7} = \frac{12}{7} = 1 + \frac{5}{7} $$

So $1$ is your next digit--we now have: $0.21..._3$, repeat:

$$ 3\cdot\frac{5}{7} = \frac{15}{7} = 2 + \frac{1}{7} $$

So now: $0.212..._3$, repeat:

$$ 3\cdot\frac{1}{7} = \frac{3}{7} = 0 + \frac{3}{7} $$

So now: $0.2120..._3$, repeat:

$$ 3\cdot\frac{3}{7} = \frac{9}{7} = 1 + \frac{2}{7} $$

Now: $0.21201..._3$, repeat:

$$ 3\cdot\frac{2}{7} = \frac{6}{7} = 0 + \frac{6}{7} $$

Now: $0.212010..._3$. But now you should recognize that we have come back to $\frac{6}{7}$ so the pattern will now start to repeat, so you have:

$$ \frac{6}{7}_{10} = 0.\overline{212010}_3 $$

We can check whether or not this is correct. The number $212010_3 = 0 + 3 + 0 + 2*27 + 1*81 + 2*243 = 624$. So the number $0.212010_3 = \frac{624}{729}$. The series then becomes:

\begin{align} \require{cancel} \frac{624}{729}\sum_0^\infty \left(\frac{1}{729}\right)^i =&\ \frac{624}{729}\frac{1}{1 - \frac{1}{729}} \\ =&\ \frac{624}{\cancel{729}}\frac{\cancel{729}}{728} \\ =&\ \frac{624}{728} \\ =&\ \frac{6\cdot \cancel{104}}{7\cdot \cancel{104}} \\ =&\ \frac{6}{7} \end{align}

So it is verified that $0.\overline{212010}_3$ is the correct representation for $\frac{6}{7}_{10}$.