Re: Base 8 counting in Gevey

> Date:         Thu, 18 Oct 2001 13:36:08 -0400
> From: Andreas Johansson <and_yo@...>
>
> Irrational complex bases are pretty near the bottom.
>
> What about base -e^2+i3e^.5 ? I'm not even going to try to write out what'd
> 100 in this 'd be in decimal ...
I've never been able to see the fun in transcendental bases --- even
though you can make rules for a unique representation of numbers, you
basically can't do arithmetic _in_ them, since any carry from one
digit position to the next will change all the digits to the right of
that as well.

(Positive, real) irrational arithmetic numbers make more sense, since
(by the definition of an arithmetic number) there will be an expansion
of one (or more) units in one position to a finite number of units in
positions to the right of that. The golden ratio will work fine as a
base, the square root of two a bit less so (see below), each allowing
you to represent a certain arithmetic extension of the rational
numbers as terminating or repeating digit sequences.

However, if you want nice (i.e., terminating) representations of the
integers, you may have to pick your arithmetic number with care, or
rather the polynomial of which it is a root --- it's not at all
obvious to me that all real arithmetic bases will behave well.

In order to have a unique or canonical representation of each number,
you also need some rules about allowable digit sequences. For the
golden ratio, for instance, the rule is that two 1's cannot follow
each other. For the square root of two, I can't think of a local rule
that will ensure that all integers come out nice.

Closely related to this are systems where you have a recurrence
relation between the positional values. The Fibonacci series can be
used as positional values, for instance --- but it's not obvious how
to extend that system for fractions.

So, just for fun, here's how to count in base the golden ratio:
        0 =    0
        1 =    1
        2 =   10.01
        3 =  100.01
        4 =  101.01
        5 = 1000.1001

There are of course many other tricks of number system representations
that can be combined with arithmetic bases: Negative bases, biased or
balanced digit sets; extended digit sets and multiple representations
to simplify calculations.

The next step up, then, are complex bases. Again, it really only makes
sense to adjoin the complex root of some polynomial, but that still
leaves some choices.

An pure imaginary base is a bit boring, I think, since it essentially
just partitions the digits into a real and an imaginary part.

For a complex root with either real and imaginary parts irrational,
the considerations above apply as well: You have to take care that
integers represent nicely.

But for me the most interesting possibility is when the base belongs
to the Gaussian ring, where the real and imaginary parts are both
integers. Especially if it will span the whole ring using a fixed set
of digits in all positions.

One semi-famous example, by Conway I think, is base i-1 using the
digits 0 and 1. The polynomial is X^2+2X+2, and we count:
        0 =         0
        1 =         1
        2 =      1100
        3 =      1101
        4 = 111010000

But any base in quadrant II or IV will actually work, with the modulus
squared giving the number of digits that is necessary.

How about 2i-1, digits -2 to 2? i-3, digits 0 to 9?
         0 =      0
         1 =      1
        ...
         9 =      9
        10 =   1540
        ...
        19 =   1549
        20 = 156080

This seems a bit unnatural to humans, but you might have a species
that doesn't think of a plane as having two dimensions...

Lars Mathiesen (U of Copenhagen CS Dep) <thorinn@...> (Humour NOT marked)