Skip to content

Balanced Ternary

Definition

Balanced ternary, also known as symmetric ternary. This is a non-standard numeral system.

In standard ternary, digits are composed of 0, 1, and 2, while in balanced ternary, digits are composed of -1, 0, and 1. Its base is also 3 (since there are three possible values). Since writing -1 as a digit is inconvenient, we will use the letter Z to represent -1.

Explanation

Here are several examples:

Decimal Balanced Ternary Decimal Balanced Ternary
0 0 5 1ZZ
1 1 6 1Z0
2 1Z 7 1Z1
3 10 8 10Z
4 11 9 100

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

Decimal Balanced Ternary
-1 Z
-2 Z1
-3 Z0
-4 ZZ
-5 Z11

It is easy to see that the highest digit of a negative number is Z, and the highest digit of a positive number is 1.

Process

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

Application One

Convert 64 to balanced ternary.

First, we rewrite the number in standard ternary:

\[ \text 64_{10} = 02101_3 \]

Let's process from the digit that has the least impact on the whole number (the least significant digit):

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

The final result is 1Z101.

Let's 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 Two

Convert 237 to balanced ternary.

First, we rewrite the number in standard ternary:

\[ \text 237_{10} = 22210_3 \]
  • 0 and 1 are skipped (since 0 and 1 are allowed in balanced ternary);
  • 2 becomes Z, and the digit to its left is incremented by 1, resulting in 23Z10;
  • 3 becomes 0, and the digit to its left is incremented by 1, resulting in 30Z10;
  • 3 becomes 0, and the digit to its left (default is 0) is incremented by 1, resulting in 100Z10;
  • 1 is skipped, resulting in 100Z10.

The final result is 100Z10.

Let's convert it back to decimal:

\[ \texttt{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\), it can be uniquely converted to a decimal number \(Y_{10}\) by multiplying each digit \(x_i\) by its corresponding weight \(3^i\).

For a decimal number \(Y_{10}\), is there a unique corresponding balanced ternary number?

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

Proof

We use proof by contradiction:

Assume a decimal number \(Y_{10}\) has two different balanced ternary numbers \(A_3\) and \(B_3\) that convert to \(Y_{10}\) when converted to decimal, i.e., we want to prove \(A_3 = B_3\). Consider the following cases:

  1. When \(Y_{10}=0\), obviously \(A_3 = B_3 = 0_3\), which contradicts the assumption.

  2. When \(Y_{10}>0\):

    • Number the digits of \(A_3\) and \(B_3\) from least significant to most significant. Let \(a_i\) be the \(i\)-th digit of \(A_3\), and \(b_i\) be the \(i\)-th digit of \(B_3\). In \(A_3\) and \(B_3\), there must exist 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, right-shift \(A_3\) and \(B_3\) by \(i\) digits to obtain \(A_3'\) and \(B_3'\). The original problem is equivalent to proving \(A_3'=B_3'\).
    • For the \(0\)-th digit of \(A_3'\) and \(B_3'\), \(a_0 \neq b_0\). Assume \(b_0 > a_0\) (the result is similar if \(a_0>b_0\)). It is easy to see that \(b_0 - a_0 \in \{1,2\}\). The contribution of digits \(i=1,2,3,\dots\) of \(A_3'\) to the value of \(A_3'\) is \(S_1 = a_1 \times 3^1 + a_2 \times 3^2+ \dots\), and the contribution of digits \(i=1,2,3,\dots\) of \(B_3'\) to the value of \(B_3'\) is \(S_2 = b_1 \times 3^1 + b_2 \times 3^2 + \dots\). Since \(A_3' = B_3'\), we have \(S_1 - S_2 = b_0 - a_0\). \(S_1\) and \(S_2\) have a common factor \(3\), but \(b_0 - a_0\) is not divisible by \(3\), which contradicts the assumption. Therefore, \(A_3'\neq B_3'\).

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

Thus, for any decimal \(Y_{10}\), there is a unique corresponding balanced ternary \(X_3\).

Practice Problems

Topcoder SRM 604 PowerOfThree

Parts of this page are translated 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.

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用