Representation of Integers in Balanced Ternary

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $n \in \Z$ be an integer.

$n$ can be represented uniquely in balanced ternary:

$\displaystyle n = \sum_{j \mathop = 0}^m r_j 3^j$
$\sqbrk {r_m r_{m - 1} \ldots r_2 r_1 r_0}$

such that:

where:

$m \in \Z_{>0}$ is a strictly positive integer such that $3^m < \size {2 n} < 3^{m + 1}$
all the $r_j$ are such that $r_j \in \set {\underline 1, 0, 1}$, where $\underline 1 := -1$.


Proof

Let $n \in \Z$.

Let $m \in \Z_{\ge 0}$ be such that:

$3^m + 1 \le \size {2 n} \le 3^{m + 1} - 1$

where $\size {2 n}$ denotes the absolute value of $2 n$.

As $2 n$ is even, this is always possible, because $3^r$ is always an odd integer for non-negative $r$.

Let $d = \dfrac {3^{m + 1} - 1} 2$.

Let $k = n + d$.

We have that:

\(\displaystyle \size {2 n}\) \(\le\) \(\displaystyle 3^{m + 1} - 1\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle \size n\) \(\le\) \(\displaystyle d\) Definition of $d$
\(\displaystyle \leadsto \ \ \) \(\displaystyle -d\) \(\le\) \(\displaystyle n \le d\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle 0\) \(\le\) \(\displaystyle n + d \le 3^{m + 1} - 1\)


Let $k = n + d \in \Z$ be represented in ternary notation:

$k = \displaystyle \sum_{j \mathop = 0}^m s_j 3^j$

where $s_j \in \set {0, 1, 2}$.

By the Basis Representation Theorem, this expression for $k$ is unique.


Now we have:

\(\displaystyle d\) \(=\) \(\displaystyle \dfrac {3^{m + 1} - 1} {3 - 1}\) by definition
\(\displaystyle \) \(=\) \(\displaystyle \sum_{j \mathop = 0}^m 3^j\) Sum of Geometric Progression


Hence we see:

\(\displaystyle n\) \(=\) \(\displaystyle k - d\) by definition
\(\displaystyle \) \(=\) \(\displaystyle \sum_{j \mathop = 0}^m s_j 3^j - \sum_{j \mathop = 0}^m 3^j\)
\(\displaystyle \) \(=\) \(\displaystyle \sum_{j \mathop = 0}^m \paren {s_j - 1} 3^j\)
\(\displaystyle \) \(=\) \(\displaystyle \sum_{j \mathop = 0}^m r_j 3^j\) where $r_j \in \set {-1, 0, 1}$


Hence $n$ has a representation in balanced ternary.

The representation for $k$ in ternary notation is unique, as established.

Hence the representation in balanced ternary for $n$ is also unique.

$\blacksquare$

Sources