View Single Post
Old 2009-02-21, 08:02   #8
only_human
 
only_human's Avatar
 
"Gang aft agley"
Sep 2002

375410 Posts
Default

"Third Base" (Chapter 10 of GROUP THEORY IN THE BEDROOM, and Other Mathematical Diversions by Brian Hayes (2008 pp 179-200, Hill and Wang)) is on Base 3 number systems and Thue sequences, originally written by him in his "Computer Science" column for American Scientist: http://www.americanscientist.org/issues/pub/third-base/, with an added afterthought on Thomas Fowler's balanced ternary calculating machine (1840!). Also added are thoughts on use of ternary in taxonomic classification trees and the Thue sequence actually studied by Axel Thue rather than the one Brian Hayes initially had illustrated in the American Scientist. Both sequences use the same substitution scheme: 0->12, 1->102, 2->0.

The scheme originally illustrated in the American Scientist starts with these stages 0,12,1020,10212012, etc. Each following stage is twice as long as the previous stage. The book's Chapter 10 afterward sequence starts with the symbol '1' and looks like this: 1, 102, 102120, 102120102012. It has the additional property that each stage is a prefix to the following stage (and the lengths double per stage but starting from a length of 3 in the 2nd stage rather than a length of 2 in that stage of the other sequence).

Knuth talks about balanced ternary in The Art of Computer Programming. Vol. 2, Seminumerical Algorithms 2nd ed. pp. 190-193 or 3rd ed. pp. 207-209.

Last fiddled with by only_human on 2009-02-21 at 08:06
only_human is offline   Reply With Quote