Editing Balanced ternary (section)

=== Ternary integer evaluation ===

Let <math>\mathcal{D}_{3}^{+}</math> be the [[Kleene plus]] of <math>\mathcal{D}_{3}</math>, which is the set of all finite length [[concatenation|concatenated]] [[String (computer science)|strings]] <math>d_n \ldots d_0</math> of one or more symbols (called its ''digits'') where <math>n</math> is a non-negative integer and all <math>n + 1</math> digits <math>d_n, \ldots, d_0</math> are taken from <math>\mathcal{D}_{3} = \lbrace \operatorname{T}, 0, 1 \rbrace.</math> The ''start'' of <math>d_n \ldots d_0</math> is the symbol <math>d_0</math> (at the right), its ''end'' is <math>d_n</math> (at the left), and its ''length'' is <math>n + 1</math>. The ''ternary evaluation'' is the function <math>v = v_{3} ~:~ \mathcal{D}_{3}^{+} \to \mathbb{Z}</math> defined by assigning to every string <math>d_n \ldots d_0 \in \mathcal{D}_{3}^{+}</math> the integer

:<math>v\left( d_n \ldots d_0 \right) ~=~ \sum_{i=0}^{n} f_{} \left( d_{i} \right) 3^{i}.</math>

The string <math>d_n \ldots d_0</math> ''represents'' (with respect to <math>v</math>) the integer <math>v\left( d_n \ldots d_0 \right).</math> The value <math>v\left( d_n \ldots d_0 \right)</math> may alternatively be denoted by <math>{d_n \ldots d_0}_{\operatorname{bal}3}.</math> 
The map <math>v : \mathcal{D}_{3}^{+} \to \mathbb{Z}</math> is [[Surjective map|surjective]] but not injective since, for example, <math>0 = v(0) = v(00) = v(0 0 0) = \cdots.</math> However, every nonzero integer has exactly one representation under <math>v</math> that does not ''end'' (on the left) with the symbol <math>0,</math> i.e. <math>d_n = 0 .</math>

If <math>d_n \ldots d_0 \in \mathcal{D}_{3}^{+}</math> and <math>n > 0</math> then <math>v</math> satisfies:

:<math>v\left( d_n d_{n-1} \ldots d_0 \right) ~=~  f_{} \left( d_{n} \right) 3^{n} + v\left( d_{n-1} \ldots d_0 \right)</math>

which shows that <math>v</math> satisfies a sort of [[recurrence relation]]. This recurrence relation has the initial condition
<math>v\left( \varepsilon \right) = 0</math> 
where <math>\varepsilon</math> is the empty string.

This implies that for every string <math>d_n \ldots d_0 \in \mathcal{D}_{3}^{+},</math>

:<math>v\left( 0 d_n \ldots d_0 \right) = v\left( d_n \ldots d_0 \right)</math>

which in words says that ''leading'' <math>0</math> symbols (to the left in a string with 2 or more symbols) do not affect the resulting value.

The following examples illustrate how some values of <math>v</math> can be computed, where (as before) all integer are written in decimal (base 10) and all elements of <math>\mathcal{D}_{3}^{+}</math> are just symbols.

:<math>\begin{alignat}{10}
v\left( \operatorname{T} \operatorname{T} \right) 
&= && f_{}\left( \operatorname{T} \right) 3^{1} + && f_{}\left( \operatorname{T} \right) 3^{0} 
&&= &&(-1) &&3 &&\,+\, &&(-1) &&1 
&&= -4 \\

v\left( \operatorname{T} 1 \right) 
&= && f_{}\left( \operatorname{T} \right) 3^{1} + && f_{}\left( 1 \right) 3^{0} 
&&= &&(-1) &&3 &&\,+\, &&(1) &&1 
&&= -2 \\

v\left( 1 \operatorname{T} \right) 
&= && f_{}\left( 1 \right) 3^{1} + && f_{}\left( \operatorname{T} \right) 3^{0} 
&&= &&(1) &&3 &&\,+\, &&(-1) &&1 
&&= 2 \\

v\left( 1 1 \right) 
&= && f_{}\left( 1 \right) 3^{1} + && f_{}\left( 1 \right) 3^{0} 
&&= &&(1) &&3 &&\,+\, &&(1) &&1 
&&= 4 \\

v\left( 1 \operatorname{T} 0 \right) 
&= f_{}\left( 1 \right) 3^{2} + && f_{}\left( \operatorname{T} \right) 3^{1} + && f_{}\left( 0 \right) 3^{0} 
&&= (1) 9 \,+\, &&(-1) &&3 &&\,+\, &&(0) &&1 
&&= 6 \\

v\left( 1 0 \operatorname{T} \right) 
&= f_{}\left( 1 \right) 3^{2} + && f_{}\left( 0 \right) 3^{1} + && f_{}\left( \operatorname{T} \right) 3^{0} 
&&= (1) 9 \,+\, &&(0) &&3 &&\,+\, &&(-1) &&1 
&&= 8 \\
\end{alignat}
</math>

and using the above recurrence relation

:<math>v\left( 1 0 1 \operatorname{T} \right) = f_{}\left( 1 \right) 3^{3} + v\left( 0 1 \operatorname{T} \right) = (1) 27 + v\left( 1 \operatorname{T} \right) = 27 + 2 = 29.</math>