[math-fun] A ternary notation
Hello SeqFan and Math-Fun, Consider this (hope this is not old-hat): 3^0 3^1 3^2 3^3 3^4 3^5 3^6 3^7 ... = 1 3 9 27 81 243 729 2187 ... This seq. is known to be very efficient if you want to weigh integer weights with a two-tray balance, leaving no "holes" behind; use weights of 1,3,9,27... units to measure all "natural" quantities, from 1 to infinity: 1 = 1 2 = 3-1 3 = 3 4 = 3+1 5 = 9-(3+1) 6 = 9-3 7 = 9-(3-1) 8 = 9-1 9 = 9 10 = 9+1 11 = 9+(3-1) 12 = 9+3 13 = 9+(3+1) 14 = 27-[9+(3+1)] etc. I had the idea, yesterday night, to represent all natural numbers in the same way -- all I had to do was to use three symbols : 0 for a power of 3 I don't need 1 for a power of 3 I need 2 as a grahic symbol meaning "minus all the rest" ... and use a regular addition rule (which will be explained below in a few seconds). Let's make first a parallel with the binary no- tation : 2^0 2^1 2^2 2^3 2^4 2^5 2^6 2^7 ... = 1 2 4 8 16 32 64 128 ... We use two symbols : 0 for a power of 2 we don't need 1 for a power of 2 we need ... and an easy addition rule. We start from the left, putting 0's and 1's where we want to, and then reverse the sequence of 0's and 1's. To represent 54 (my age) we look for the closest power < or = to 54 and mark it with a "1": 2^0 2^1 2^2 2^3 2^4 2^5 2^6 2^7 ... = 1 2 4 8 16 32 64 128 ... --> 1 54 - 32 = 22; we mark with another "1" the closest power < or = to 22: 2^0 2^1 2^2 2^3 2^4 2^5 2^6 2^7 ... = 1 2 4 8 16 32 64 128 ... --> 1 1 54 - (32+16) = 6, we mark accordingly 2^2: 2^0 2^1 2^2 2^3 2^4 2^5 2^6 2^7 ... = 1 2 4 8 16 32 64 128 ... --> 1 1 1 54 - (32+16+4) = 2, we mark 2^1: 2^0 2^1 2^2 2^3 2^4 2^5 2^6 2^7 ... = 1 2 4 8 16 32 64 128 ... --> 1 1 1 1 To complete the binary representation of 54, we put 0's under all unnecessary powers: 2^0 2^1 2^2 2^3 2^4 2^5 2^6 2^7 ... = 1 2 4 8 16 32 64 128 ... --> 0 1 1 0 1 1 ... last line is reversed to produce 110110, which is indeed the binary expression of 54. We can represent all natural integers with this method, of course: 2^0 2^1 2^2 2^3 2^4 2^5 2^6 2^7 ... = 1 2 4 8 16 32 64 128 ... 1 = 1 => 1 2 = 0 1 (to reverse)=> 10 3 = 1 1 => 11 4 = 0 0 1 => 100 5 = 1 0 1 => 101 6 = 0 1 1 => 110 7 = 1 1 1 => 111 8 = 0 0 0 1 => 1000 9 = 1 0 0 1 => 1001 etc. Let's do the same with the powers of 3; we will mark with a "1" the powers we need, with a "0" the ones we will discard and (novelty!) with a "2" the quantity we will substract (I will use the star symbol (*) to indicate hereunder an operation in base 10): 3^0 3^1 3^2 3^3 3^4 3^5 3^6 3^7 ... = 1 3 9 27 81 243 729 2187 ... 1 = 1 2 = *3-1* = 121 3 = 01 => 10 4 = *3+1* = 11 5 = *9-4* = 1211 6 = *9-3* = 1210 7 = *9-2* = 12121 8 = *9-1* = 1201 9 = 001 => 100 10 = *9+1* = 101 11 = *9+2* = 1121 12 = *9+3* = 110 13 = *9+4* = 111 14 = *27-13* = 12111 15 = *27-12* = 12110 16 = *27-11* = 121121 17 = *27-10* = 12101 18 = *27-9* = 12100 19 = *27-8* = 121201 20 = *27-7* = 1212121 21 = *27-6* = 121210 22 = *27-5* = 121211 23 = *27-4* = 12011 24 = *27-3* = 12010 25 = *27-2* = 120121 26 = *27-1* = 12001 27 = 0001 => 1000 28 = *27+1* = 1001 29 = *27+2* = 10121 30 = *27+3* = 10010 etc. Is this of interest? Is the introduction of a third symbol "economi- cally" efficient? (I think we will use less symbols to represent all first 1000 natural integers with this "ternary notation" than with the usual binary system -- the price might be to high, though)... Speaking of "notation efficiency" (how to re- present in the less "symbol-consuming" way all the natural numbers) -- is there a definitive answer? The "ternary notation" above can certainly be bettered as the "ternary artefacts" 20, 1220, 001 or 002 represent nothing. Best, É. (seq. 0,1,121,10,11,1211,1210,12121,1201,100,... is not in the OEIS)
Eric Angelini wrote:
Hello SeqFan and Math-Fun, Consider this (hope this is not old-hat):
3^0 3^1 3^2 3^3 3^4 3^5 3^6 3^7 ... = 1 3 9 27 81 243 729 2187 ...
This seq. is known to be very efficient if you want to weigh integer weights with a two-tray balance, leaving no "holes" behind; use weights of 1,3,9,27... units to measure all "natural" quantities, from 1 to infinity:
<snip>
Let's do the same with the powers of 3; we will mark with a "1" the powers we need, with a "0" the ones we will discard and (novelty!) with a "2" the quantity we will substract
In a way, this is also consistent and appropriate, as 2 is -1 mod 3.
(I will use the star symbol (*) to indicate hereunder an operation in base 10):
3^0 3^1 3^2 3^3 3^4 3^5 3^6 3^7 ... = 1 3 9 27 81 243 729 2187 ...
1 = 1 2 = *3-1* = 121 3 = 01 => 10 4 = *3+1* = 11 5 = *9-4* = 1211 6 = *9-3* = 1210 7 = *9-2* = 12121 8 = *9-1* = 1201 9 = 001 => 100
Why 2 is not marked just as 12 (i.e. +1*3 + -1*1 ?) And then 3 = 10, 4 = 11 as you have given, but 5 = +1*9 + -1*3 + -1*1 = 122 6 = +1*9 + -1*3 + 0*1 = 120 7 = +1*9 + -1*3 + 1*1 = 121 8 = +1*9 + 0*3 + -1*1 = 102 9 = +1*9 + 0*3 + 0*1 = 100 I am sorry, but the terms 1,12,10,11,122,120,121,102,100 do not match anything in the table.
The "ternary notation" above can certainly be bettered as the "ternary artefacts" 20, 1220, represent nothing.
No. They represent negative integers: -1 = -1*1 = 2 -2 = -1*3 + 1*1 = 21 -3 = -1*3+0*1 = 20 -4 = -1*3 + -1*1 = 22 -5 = -1*9 + 1*3 + 1*1 = 211 -6 = -1*9 + 1*3 + 0*1 = 210 -7 = -1*9 + 1*3 + -1*1 = 212 -8 = -1*9 + 0*3 + 1*1 = 201 -9 = -1*9 + 0*3 + 0*3 = 200 We see that to convert an integer to its negative in this notation, we have just to swap ones and twos 1 <-> 2, and keep zeros intact. I am sorry, but the terms 2,21,20,22,211,210,212,201,200 do not match anything in the table. Now, of course any such ternary string (either 0, or beginning with a non-zero digit, i.e. either 1 or 2) represents non-negative integers in the usual ternary notation: http://www.research.att.com/projects/OEIS?Anum=A007089 And because I'm looking for bijections everywhere, even simple ones, one expects two to be lurking here. We just need to "fold" the integers to natural numbers with f: Z -> N as given by f(z) = 2z if z>0 else 2|z|+1, and vice versa, with its inverse* *g(z) = z/2 if z even else (1-z)/2. So we get those two sequences (for positive and negative integers) interleaved: I am sorry, but the terms 0,1,2,12,21,10,20,11,22,122,211,120,210,121,212,102,201,100,200 do not match anything in the table. Reinterpreting them in ordinary ternary notation, we get: I am sorry, but the terms 0,1,2,5,7,3,6,4,8,17,22,15,21,20,16,23,11,19,9,18, do not match anything in the table. And actually, this seems to be an involution (self-inverse permutation), so we get just one permutation, not two. Why is this? (Or is it?) I have to think about it, but first I will finish my coffee to raise my IQ temporarily from that of the greater apes. Salut, Regards, Groetjes, Terveisin, Antti
Best, Ã.
(seq. 0,1,121,10,11,1211,1210,12121,1201,100,... is not in the OEIS)
Eric Angelini wrote:
Is the introduction of a third symbol "economi- cally" efficient? (I think we will use less symbols to represent all first 1000 natural integers with this "ternary notation" than with the usual binary system -- the price might be to high, though)...
You're coming up with a variation on what's called "balanced ternary" notation, base 3 with digits {1,0,-1}. There are too many possible conventions for how to write this using the digits {0,1,2} instead; the EIS entry A072998 does it by adding 1 to each digit. Yes, base-3 computers (built on "trits", not "bits") were indeed pursued before binary ones became universal. Christoph is quite right in his recollection that "base e" is optimal, and base 3 is the best integer choice, if it weren't for the physical simplicity of 2-state storage. American Scientist had an article recently with some base-3 history: http://www.americanscientist.org/template/AssetDetail/assetid/14405/page/1 Two particularly nice properties of trits are that (1) a single trit can hold a determination of <=>, and (2) there's a tritwise operation analogous to xor, well-known now as the rule of the award-winning children's card game "Set": if a=b, then a#b is a, and if a!=b, then a#b is the third state, c. (Or, a#b is -a-b mod 3, if you prefer.) --Michael Kleber (I'm suppressing an odd urge to include a middle name in my signature, to go with the rest of the 3-not-2 theme...) -- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.
Another property of the # operator, analogous to xor: It satisfies the rule (X#Y)#X = X#(Y#X) = Y. This is the rule for Semisymmetric Quasigroups, which I temporarily called Babagroups last year, and which Don Knuth calls Gropes. Incidentally, I received a couple of stone tablets from DEK this summer, mostly about Gropes. I'll get them transcribed here someday. Rich -----Original Message----- From: math-fun-bounces+rschroe=sandia.gov@mailman.xmission.com on behalf of Michael Kleber Sent: Thu 9/15/2005 7:08 AM To: math-fun Subject: Re: [math-fun] A ternary notation Eric Angelini wrote: <snip: base 3 stuff> Two particularly nice properties of trits are that (1) a single trit can hold a determination of <=>, and (2) there's a tritwise operation analogous to xor, well-known now as the rule of the award-winning children's card game "Set": if a=b, then a#b is a, and if a!=b, then a#b is the third state, c. (Or, a#b is -a-b mod 3, if you prefer.) --Michael Kleber (I'm suppressing an odd urge to include a middle name in my signature, to go with the rest of the 3-not-2 theme...) -- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
It's quite common in computer arithmetic units to "recode" a base-2 number using _three_ digits: +1, 0, -1. Thus, although the number is still in base 2, this "balanced" representation has much better rounding behavior, since ignoring the lower order digits always gives the correctly rounded value. Multiplier hardware, in particular, likes this representation. There's been a huge amount of research into various number systems & representations for computer arithmetic, which research continues to this day. Here's a start: http://arith.stanford.edu/
in a similar vein, I tried to properly define the distinct partitions of n into + or - powers of two. Like counting the ways to pay n (bin-euro's) with getting change allowed: example: 13 ways to pay 4000 bin-euro's using distinct coins and getting change: {l[32] + l[128] + l[256] + l[512] + l[1024] + l[2048], -l[32] + l[64] + l[128] + l[256] + l[512] + l[1024] + l[2048], -l[32] - l[64] + l[4096], l[32] - l[128] + l[4096], -l[32] + l[64] - l[128] + l[4096], l[32] + l[128] - l[256] + l[4096], -l[32] + l[64] + l[128] - l[256] + l[4096], l[32] + l[128] + l[256] - l[512] + l[4096], -l[32] + l[64] + l[128] + l[256] - l[512] + l[4096], l[32] + l[128] + l[256] + l[512] - l[1024] + l[4096], -l[32] + l[64] + l[128] + l[256] + l[512] - l[1024] + l[4096], l[32] + l[128] + l[256] + l[512] + l[1024] - l[2048] + l[4096], -l[32] + l[64] + l[128] + l[256] + l[512] + l[1024] - l[2048] + l[4096]} This has a pretty fractal structure: Drop[CoefficientList[ExpandAll[ x^(2^13-1)Product[1+l[i]x^(2^i),{i,0,12}] Product[1+1/l[i]1/(x^(2^i)),{i,0,12}]] ,x] ,2^13]; Trouble is that the above 13 ways depend on the largest coins allowed (here 2^12). So there is no limiting sequence for such type of problem. If only 1 coin can be given as change, then the count seems to be A000120, or simply the number of ones in the binary repr. of n. Booooring! W. ----- Original Message ----- From: "Henry Baker" <hbaker1@pipeline.com> To: <michael.kleber@gmail.com>; "math-fun" <math-fun@mailman.xmission.com> Sent: Thursday, September 15, 2005 5:27 PM Subject: Re: [math-fun] A ternary notation It's quite common in computer arithmetic units to "recode" a base-2 number using _three_ digits: +1, 0, -1. Thus, although the number is still in base 2, this "balanced" representation has much better rounding behavior, since ignoring the lower order digits always gives the correctly rounded value. Multiplier hardware, in particular, likes this representation. There's been a huge amount of research into various number systems & representations for computer arithmetic, which research continues to this day. Here's a start: http://arith.stanford.edu/ _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (6)
-
Antti Karttunen -
Eric Angelini -
Henry Baker -
Michael Kleber -
Schroeppel, Richard -
wouter meeussen