Converting from base $2$ to base 3

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$?

• If you want to go directly from base 2 to base 3, then it can be a little complicated. The "usual" way is to convert to base 10, then to base 3. It's always possible to convert a terminating base 2 number to a terminating base 10 number (this is because $10$ is divisible by $2$). Which do you prefer? The direct route (difficult) or the "easy" route (which requires an intermediate step). Either way, you're going to end up multiplying by $3$, so either you convert to base 10 and then start multiplying by $3$ or you start multiplying your expression by $11_2$. – Jared Jun 13 '16 at 20:13
• @Jared I already found $y$ in base $10$. I am wondering how to get it in base 3. – Puzzled417 Jun 13 '16 at 20:14

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.

• You don't have to guess if you know that $3$ is a primitive root mod $7$. See en.wikipedia.org/wiki/… – Barry Cipra Jun 13 '16 at 20:18
• @BarryCipra Thanks for the suggestion! I've edited my answer at the end above. – Noble Mushtak Jun 13 '16 at 20:26
• 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$. – Noble Mushtak Jun 13 '16 at 20:32

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.

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}$.