Balanced Ternary

Definition

Balanced ternary, also called symmetric ternary, is a generalized positional numeral system.

The digits of ordinary ternary consist of 0,1, and 2, while the digits of balanced ternary consist of -1,0, and 1. Its base is also 3 (because there are three possible values). Since writing -1 as a digit is inconvenient, we use the letter Z to represent -1.

Explanation

Here are several examples:

Representing negative numbers in this numeral system is easy: simply reverse the digits of the positive number (Z becomes 1, and 1 becomes Z).

It is easy to see that the most significant digit of a negative number is Z, while that of a positive number is 1.

Process

In the conversion method for balanced ternary, first write a given number x in ordinary ternary. When x is represented in ordinary ternary, each digit is 0, 1, or 2. Starting from the least significant digit, we can skip any 0 and 1, but if we encounter 2, we should first change it to Z and add 1 to the next digit. When we encounter digit 3, it should be changed to 0 and 1 should be added to the next digit.

Application 1

Convert 64 to balanced ternary.

First, rewrite the number in ordinary ternary:

$$\text 64_{10} = 02101_3$$

Let us process the digits with the smallest effect on the whole number first (the least significant digit):

• 101 is skipped (because 0 and 1 are allowed in balanced ternary);
• 2 becomes Z, and the digit to its left is increased by 1, giving 1Z101;
• 1 is skipped, giving 1Z101.

The final result is 1Z101.

We then convert it back to decimal:

$$\texttt {1Z101}=81 \times 1 +27 \times (-1) + 9 \times 1 + 3 \times 0 + 1 \times 1 = 64_{10}$$

Application 2

Convert 237 to balanced ternary.

First, rewrite the number in ordinary ternary:

$$\text 237_{10} = 22210_3$$

• 0 and 1 are skipped (because 0 and 1 are allowed in balanced ternary);
• 2 becomes Z, and the digit to its left is increased by 1, giving 23Z10;
• 3 becomes 0, and the digit to its left is increased by 1, giving 30Z10;
• 3 becomes 0, and the digit to its left (defaulting to 0) is increased by 1, giving 100Z10;
• 1 is skipped, giving 100Z10.

The final result is 100Z10.

We then convert it back to decimal:

$$\mathtt{100Z10} = 243 \cdot 1 + 81 \cdot 0 + 27 \cdot 0 + 9 \cdot (-1) + 3 \cdot 1 + 1 \cdot 0 = 237_{10}$$

Properties

For a balanced ternary number $X_3$, multiplying each digit $x_i$ by its corresponding weight $3^i$ uniquely produces a decimal number $Y_{10}$.

For a decimal number $Y_{10}$, does it uniquely correspond to one balanced ternary number?

The answer is yes. This property is called the uniqueness of balanced ternary.

Proof

We use proof by contradiction:

Suppose a decimal number $Y_{10}$ has two different balanced ternary numbers $A_3,B_3$ that convert to $Y_{10}$; that is, we need to prove $A_3 = B_3$. We discuss cases:

1. When $Y_{10}=0$, clearly $A_3 = B_3 = 0_3$, contradicting the assumption.

2. When $Y_{10}>0$:

   • Number the digits of $A_3$ and $B_3$ from low to high, and let $a_i$ be the digit of $A_3$ at position $i$, and $b_i$ be the digit of $B$ at position $i$. In $A_3,B_3$, there must be an $i$ such that $a_i\neq b_i$. It can be seen that digits $i-1,i-2,\dots,0$ are irrelevant to the proof. Therefore, shift $A_3,B_3$ right by $i$ digits to obtain $A_3',B_3'$; the original problem is equivalent to proving $A_3'=B_3'$.
   • For $A_3',B_3'$'s digit $0$, $a_0 \neq b_0$. Assume $b_0 > a_0$ (the result is the same when $a_0>b_0$). Clearly $b_0 - a_0 \in \{1,2\}$. For $A_3'$, the contribution of its digits $i=1,2,3,\dots$ to $A_3'$'s value is $S_1 = a_1 \times 3^1 + a_2 \times 3^2+ \dots$, and for $B_3'$, the contribution of its digits $i=1,2,3,\dots$ to $B_3'$'s value is $S_2 = b_1 \times 3^1 + b_2 \times 3^2 + \dots$. Since $A_3' = B_3'$, we obtain $S_1 - S_2 = b_0 - a_0$. $S_1,S_2$ have a common factor of $3$, while $b_0 - a_0$ is not divisible by $3$, contradicting the assumption. Therefore, $A_3'\neq B_3'$.

3. When $Y_{10}<0$, the proof is the same as for $Y_{10}>0$.

Thus, every decimal $Y_{10}$ has a unique corresponding balanced ternary $X_3$.

Practice Problem

Topcoder SRM 604 PowerOfThree

Part of this page is adapted from the blog post Троичная сбалансированная система счисления and its English translation Balanced Ternary. The Russian version is licensed under Public Domain + Leave a Link; the English version is licensed under CC-BY-SA 4.0.