[Math] Find algorithm for converting number to Balanced ternary

algorithms

I have this math question, I have to find an algorithm that is able to convert any number to balanced ternary.

Balanced ternary is like ordinary base $3$ in the sense that the
positions are weighted by the powers $3^0, 3^1, 3^2,\cdots$ However,
the digits represent, not $0,1$ and $2$, but $0, 1$ and $-1$. We will
write $\bar{1}$ for the digit representing $-1$. Thus for example
$1\bar{1}001\bar{1}$ represents $$3^5−3^4+3^1−3^0 =243−81+3−1=164$$
The result is that both negative and positive values can be
represented in this system.

So far I recognized that $n\equiv k\pmod{3}$, where $k\in\{-1, 0, 1\}$ ($k=2\equiv -1\pmod{3}$). $k$ represents the lowest bit, aka the rightmost. I also recognized that for any positive number, the leftmost digit is $1$ and for any negative number the leftmost digit is $\bar{1}$. Also, the negative of any number is the bits flipped. i.e $-(\bar{1}11\bar{1}) = 1\bar{1}\bar{1}1$ That's all I recognized so far. I can't figure out how to find the middle digits. Thanks.

Best Answer

Hint: What can we do if we know that the lowest digit is $0$?

Since the lowest digits is $0$, it means that the number is divisible by 3. As such, let's try dividing by 3. It would produce a new number, which in balanced ternary, would be the rest of the digits of the original number in balanced ternary.

What if the lowest digit is not $0$?

If it is $1$, we can subtract $1$ from the original number to make it $0$, so we can use what we have above to get the rest of the digits. Otherwise, if is $\bar1$, so we can add $1$ to make it end in $0$, preserving the rest of the digits.

How does it scale?

We can find the lowest digit of the new number, and this is the second-lowest digit of the original number. Likewise, we can find the second-lowest digit of this number, by induction, which means we can find the third-lowest digit of the original number, continuing which, we find all the digits of the original number.

Example:

Let's use $8$ as an example here.

 

Since $8\equiv-1\pmod3$, the lowest digit is $\bar1$. We add one to $8$ to make that digit $0$. Dividing by $3$, we get $3$, which represents the rest of the digits. Since $3\equiv0\pmod3$, the second-lowest digit is $0$. Dividing by $3$, we get $1$, which represents the rest of the digits. Since $1$ is represented as $1$, we are done. Writing out all the digits we found, we have $10\bar1$, which is the balanced ternary representation of 8.

Related Question