Algorithm for Converting Non-balanced Base-n to Balanced Base-n (for odd n)

For an "ordinary" base-$n$ representation using digits $0,\ldots,n-1,$ a number $x$ with $k+1$ digits and no negative sign will have a leading digit $d$ (a $d$ in the "$n^k$" place) under exactly the following conditions:

$$ 0 \leq x - dn^k < n^k.$$

The greatest possible value of a number of $k+1$ digits is

$$ (n-1)n^k + (n-1)n^{k-1} + \cdots + (n-1)n^2 + (n-1)n + (n-1) = n^{k+1} - 1.$$

For a balanced base-$n$ representation where $n$ is odd, a number $x$ with $(k+1)$ digits will have a leading digit $d$ when

$$ -\frac{n^k}{2} < x - dn^k < \frac{n^k}{2}.$$

In this case there is no possibility of equality, since $x - dn^k$ is an integer and $\frac{n^k}{2}$ is not. The greatest possible value of a number of $k+1$ digits is

$$ \frac{n-1}{2}n^k + \frac{n-1}{2}n^{k-1} + \cdots + \frac{n-1}{2}n^2 + \frac{n-1}{2}n + \frac{n-1}{2} = \frac{n^{k+1} - 1}{2}$$

and similarly the least possible value is $-\frac{n^{k+1} - 1}{2}.$

For any odd $n,$ then, you can convert an ordinary base-$n$ number whose digits are $c_p\cdots c_2c_1c_0$ to a balanced base-$n$ number whose digits are $d_q\cdots d_2d_1d_0$ by working from right to left, much like the way you would convert ordinary ternary to balanced ternary. That is, if you have already converted the rightmost $k$ digits of a number $x$, you will have $$ x = (c_p\cdots c_{k+1}c'_k)n^k + (d_{k-1}\cdots d_1d_0) $$ where $-\frac{n^k}{2} < d_{k-1}\cdots d_1d_0 < \frac{n^k}{2}$ and $c'_k$ is either the original $c_k$ or $c_k + 1.$ (The number $d_{k-1}\cdots d_1d_0$ will be negative if its most significant non-zero digit is negative; it is possible for this number to have some leading zeros.)

Now write the number $x$ this way: $$x = (c_p\cdots c_{k+2})n^{k+2} + c_{k+1}n^{k+1} + c_kn^k + (d_{k-1}\cdots d_1d_0).$$ If $c_k < \frac n2,$ then $c_kn^k + (d_{k-1}\cdots d_1d_0) < \frac{n^{k+1}}{2}$, so you can set $d_k = c_k$ and write $$ x = (c_p\cdots c_{k+1})n^{k+1} + (d_kd_{k-1}\cdots d_1d_0). $$ If $c_k > \frac n2,$ then $c_kn^k + (d_{k-1}\cdots d_1d_0) > \frac{n^{k+1}}{2}$, so you will need to set $d_k = c_k - n$ so that you can write $$\begin{eqnarray} x &=& (c_p\cdots c_{k+2})n^{k+2} + (c_{k+1}+1)n^{k+1} + (d_kd_{k-1}\cdots d_1d_0)\\ &=& (c_p\cdots c_{k+2}c'_{k+1})n^{k+1} + (d_kd_{k-1}\cdots d_1d_0) \end{eqnarray}$$ where $c'_{k+1} = c_{k+1} + 1.$ That is, if you would "round up" from $c_k$ then you "carry $1$" to $c_{k+1}.$

For the rightmost digit, $c_0,$ of course, there are no digits to the right of it, so $c'_0=c_0$ and you can omit $d_{k-1}\cdots d_1d_0$ when you apply the formulas above. For the leftmost digit, $c_p,$ there is no digit $c_{p+1}$ to "carry" to, so if $c_p > \frac n2$ you simply set $d_p = c_p - n$ and $d_{p+1} = 1$ and you're done.