Conference rusure::math

To convert to balanced ternary, you replace all '2's by writing '!' and adding
one to the next digit to the left. So 35+2/9 in ternary is 1022.02 -> 1022.1!
-> 10(3)!.1! - > 110!.1!


a==b mod m (read '==' as 'is congruent to') means (a-b) is exactly divisible
by m. Another way of saying this is that
	a = a1*m + a2 and b = b1*m + b2 and a2 = b2.
A little algebra on the congruences in this form will sow why I and II are
correct. III fails if n is a divisor of m; for example,
	25 == 20 mod 5, but
	(25/5 = 5) =/= (20/5 = 4) mod 5 (read =/= as 'is NOT congruent to').

Lynn

Expanding on .-1: I should have added, a2<m and b2<m. Also, while
	17 == 6 mod 11,
	17/2 =/= 6/2 mod 11 does not even conform to the condition that all
the numbers be integers.

Re .1, .2:

Well, I wrote my reply already, and I don't want to waste it, so here is
another explanation:

It looks like the balanced ternary number system is analogous to the more
familiar systems.  For example, in normal decimal, 345 = 3*10^2 + 4*10^1 +
5*10^0.  In normal ternary, 102 = 1*3^2 + 0*3^1 + 2*3^0 = 11.  In balanced
ternary, 10! = 1*3^2 + 0*3^1 + -1*3^0 = 8.  So converting from balanced ternary
to decimal is simple, just follow the above pattern.

To convert the other way, convert the number to normal ternary.  Add
...111.11... to the number, where the number of 1's on each side of the
ternary point is selected to equal the number of significant digits in the
ternary number.  Do this addition with normal ternary addition.  Now subtract
the same number, ...111.11..., from the result, but do the subtraction
digit-by-digit; 2 becomes 1, 1 becomes 0, 0 becomes !.  The result will be
the balanced ternary representation of the original number.  (Note that there
may be one more significant digit in the number being subtracted from than the
original number that was added to, because of a carry in the addition, but that
digit should not change during the subtraction.)

For 35 and 2/9, write the ternary representation:

	1*27 + 0*9 + 2*3 + 2*1 + 0*1/3 + 2*1/9 = 1022.02 (ternary).

Add 1111.11:

	1022.02 (ternary) + 1111.11 (ternary) = 2210.20 (ternary).

Subtract, digit-by-digit, 1111.11:

	2210.20 (ternary) - (sort of) 1111.11 = 110!.1! (balanced ternary).


For the second problem, consider the definition of modular congruence:  a ==
b (mod m) iff there exists an integer k such that a+km = b.

Now, if a == b (mod m), then there exists an integer k such that a+km = b.
And if x == y (mod m), then there exists an integer l such that x+lm = y.

Adding the two equations gives us a+km + x+lm = b + y, so a+x + (k+l)m = b+y.
Clearly, k+l is an integer, so a+x == b+y (mod m), by definition of modular
congruence.

Similarly, (a+km)(x+lm) = by, so ax + (kx+al+klm)m = by, and kx+al+klm is an
integer, so ax == by (mod m).

Finally, the last statement can be disproved by example.  Consider that 2 == 4
(mod 2), but 2/2 is not congruent to 4/2 modulo 2, since there obviously is
no integer such that 1 + 2k = 2.


				-- edp

Here's another method (perhaps the more traditional one) of
converting numbers to balanced ternary.  We handle the integer
and fractional parts separately.

To convert an integer to another base, keep dividing by the base
and note the remainders.  Stop when the result is 0.

To convert 35 to balanced base 3, do the following:

35 divided by 3 is 12 with a remainder of (((-1))).
12 divided by 3 is  4 with a remainder of ((( 0))).
 4 divided by 3 is  1 with a remainder of ((( 1))).
 1 divided by 3 is  0 with a remainder of ((( 1))).
					      ^
Read the remainders backwards ----------------| to get the answer of 110!.

To convert a fraction to balanced ternary, keep multiplying by the base
and note the integer parts. (Keep the fractional parts between -1/2 and +1/2).
Stop when the remainder is 0.

 2/9 times 3 is 2/3 = ((( 1))) with a remainder of -1/3.
-1/3 times 3 is -1  = (((-1))) with a remainder of 0.
			  ^
Read the integer parts ---| in order to get the answer of .1!.

[The methods given earlier are probably better.]

Here is the way I convert numbers to balanced ternary:
(This need does not come up too often in everyday life.)

[	1000 represents 27	!000 represents -27
	 100 represents  9	 !00 represents  -9
	  10 represents  3	  !0 represents  -3
	   1 represents  1	   ! represents  -1
	.1   represents  1/3	.!   represents  -1/3
	.01  represents  1/9	.0!  represents  -1/9
	and so on.]

I convert numbers by repeatedly finding the power of 3 (or negation)
that is the closest to the number.  Repeat this after subtracting
away the power of 3, and stop when the difference between the remainder
and zero is small enough.  The result is the sum of the representations
of the powers of 3--there is at most non-zero element in each column.

For 35 2/9:
	35 + 2/9	27 is closest	1000
	 8 + 2/9	 9 is closest	 100
	-1 + 2/9	-1 is closest	   !
	     2/9       1/3 is closest	    .1
	   - 1/9      -1/9 is closest	    .0!
					-------
			result		110!.1!
For 1/2:
	1/2		1/3 is closest	.1
	1/6		1/9 is closest	.01
	1/18		1/27 is closest .001
	1/54		1/81 is closest .0001
					-----
			result		.1111111111111111111...
 
The normal scheme for base conversion is to find the largest power
smaller than the number rather than the closest power.  [To convert
a number to base n, you actually look for the largest number of the
form  {1,2,...,n-1}*n^i (for integer i)  that is smaller than the number.
To convert to balanced base 2*n+1 you look for the closest number of
the form  {-(n-1),...,-2,-1,1,2,...,n-1}*n^i (for integer i)  closest
to the number.]

Another balanced ternary representation for 1/2 is 1.!!!!!!!!!...
For `normal' number systems, numbers that can be expressed exactly
have multiple representations (like 1.0 and .99... in decimal,
1.0 and 0.22... in ternary).  However, I believe that for balanced
bases the only numbers with multiple representations are those that
can not be expressed exactly in the base.  (Is this true?)

						B.J.

Thanks for all the responses! 

It turned out there were no balanced ternary number questions on the GRE
Computer Science subject test that I took. Likewise, there were no modular
congruence questions.

Jack 

Neat use for "balanced ternary":  Consider constructing sets of weights that
can be used to exactly weigh anything up to some maximum on a balance.  If
the weights and object to be weighed must go on opposite sides of the balance,
the best set of weights - assuming only one of each size - is powers of 2;
you just write out the binary representation to figure out which weights
you need.

If you are allowed to put weights on BOTH sides of the scale, you can get away
with weights in units of powers of 3; now, you write out a balanced ternary
representation, put "1"'s across from the object being weighed, "!"'s on the
same side.

I discovered this back in high school, trying to answer a question on minimal
sets of weights for weighing in various situations.
							-- Jerry