Find algorithm for converting number to Balanced ternary 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.
 A: 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.

A: As you recognized, it suffices to have an algorithm for positive numbers, so I’ll consider a positive integer $m$. The largest number that can be represented with $n$ digits of balanced ternary is
$$\sum_{k=0}^{n-1}3^k=\frac{3^n-1}{3-1}=\frac12\left(3^n-1\right)\;,$$
so we want the largest $n$ such that $\frac12(3^n-1)<m$, or $3^n<2m+1$; this is 
$$n=\left\lfloor\log_32m\right\rfloor\;.$$
The number is going to be $m=(d_nd_{n-1}\ldots d_0)$, where $d_n=1$, and $(d_{n-1}\ldots d_0)$ represents $m-3^n$. Now repeat the process on $|m-3^n|$, flipping the sign if necessary. Since $|m-3^n|<m$, the process terminates.
