rebase or debase? (long!)

[Marc LeBrun]

This is an advertisement for a very useful "rebasing" operator that I think 
should be adopted as some kind of a "standard".

Lately I've taken to writing this "rebasing" operation as

   b [n] q

pronounced "rebase n from b to q" (with "base" b, "index" n and "argument" q).

This operation can be described informally as "expand n in base b, then 
treat the digits as though it's base q instead".

For example

   2 [5] 10  =  101

because

   5 = 1 (2^2) + 0 (2^1) + 1 (2^0)

in base 2, so this becomes

   1 (10^2) + 0 (10^1) + 1 (10^0) = 101

Note that the "101" is the perfectly ordinary value "one-hundred one", 
written in decimal as usual, and not a binary string.

A simple implementation of rebase might be

   rebase(b, n, q):=
     if n = 0
       then 0
       else remainder(n,b) + q * rebase(b, quotient(n,b), q);

(Just being able to conveniently look at numbers in different bases might 
be enough justification to add "rebase" to your computer algebra library!)

Obviously we can go the other way too

   10 [101] 2  =  5

and so invert the previous rebasing operation.  However we can also rebase 
numbers with decimal digits other than 0 and 1 into base 2 as well:

   10 [89] 2  =  8 (2^1) + 9 (2^0)  =  25.

So there's an infinite two-parameter family of simple rebasing sequences 
defined by

   a(n)  =  b [n] q

A bunch of these are already in the EIS--such as 2[n]4, the Moser-de Bruijn 
sequence, A000695.  I've also recently Sloaned a few of the more 
interesting ones described here--such as its converse, 4[n]2, now entered 
as A065362.  (Feel free to add more!<;-)

The above example illustrates that rebasing is not merely a "syntactic" 
operation on digit strings, but truly maps quantities.  It brings a lot of 
common but "unorthodox" operations into a standard framework.  For example,

   10 [n] 1  and  2 [n] 1

respectively are the sum of the decimal digits and bits in n.

Furthermore we need not restrict it to positive integers:

   -2 [n] 2  and  -2 [-n] 2  and  2 [n] -2

convert between "negabinary" and binary, while

   10 [n] 1/10  and  2 [n] 1/2

respectively reverse the digits and bits in n (please scale to taste).

Interesting digressions arise with non-integral index.  For example

   2 [x] 1

is integral for dyadic rational x and infinite otherwise, while the bit 
reversing

   2 [x] 1/2

is closed in the 2-adics.  With q > b we stretch the reals apart:

   2 [x] 3

is Cantorish (for x "surreal" is 2[x]3 "continuous"?) while q < b crunches 
things together in ways I find hard to visualize.  Can you describe

   3 [x] 2

for instance?  (Is it anywhere piecewise continuous?)

Moreover the parameters need not even be ordinary numbers, which leads to 
all sorts of interesting stuff.  For example

   2 [n] (x)

are the polynomials (or power series) in x whose coefficients are 0 or 1.

Ultimately, the "base" and "argument" can be extended to symbols that 
indicate both the basis and coefficient system.  For example

   Z2 [n] (x)

would indicate the polynomials in x, mod 2 or

   <3> [n] q

might denote expansion of n in "balanaced ternary" instead of vanilla base 3.

This is particularly handy for "umbral" unit bases.  For example we can write

   F [n] 2

meaning "expand n in Fibonacci numbers (ala Zeckendorf) then rebase into 
binary", giving the "Fibbinary" numbers, A003714.

Note that a rebased representation may need to be "adjusted" via 
equivalence transformations to conform to the canonical format of the 
domain.  For example

   2 [n] F

may have to be diddled to "ripple" adjacent bits via

   F[n] + F[n+1]  =  F[n+2]

(or alternatively

   F^(n) + F^(n+1)  =  F^(n+2)

in "umbral" style) to make a legal Zeckendorf expansion, much as 10[89]2 
"ripples" in binary.  (Many recurrence sequences can be represented in this 
"umbral" way, with the base essentailly being equivalent to a special 
matrix or similar algebraic object).

Using such a rebasing and its inverse we can also define nice transforms of 
arithmetic operations:

   q [ b[i]q + b[j]q ] b

defines an operation on i and j in the b-domain via its image "+" in the 
q-domain.

When b and q are given by context with i and j integral, I like to simplify 
the notation to just [i] + [j], calling this a "numbral 
arithmetic".  Numbrals "look just like numbers" but behave 
differently.  This was inspired as a generalization of Conway and Guy's 
"nimbers" (the square brackets are then just ASCII for the red font used in 
the "Book of Numbers").

Going to symbolic extremes, we can perhaps even stretch rebasing to denote 
substitution or "expression application" (ala the lambda calculus).  For 
example

   x[f(x)]y  =  f(y)

"changes variables" in the expression f from x to y, or "evaluates" the 
function f(x) at x=y.

All this is of course just an attempt to unify a bunch of frequently used 
stuff, such as binary expansions, digit reversals, funny arithmetics, etc 
into a common framework with a standardized notation.

Adopting something along these lines would simplify and clarify many EIS 
descriptions.  For example I'm now sensitized to the phrase "...converted 
to decimal".  This is often completely unnecessary when the elements are 
already true numerical magnitudes, since that's the assumed notation for 
integers anyway.  In other cases explicitly applying some a(n)-->b[a(n)]10 
would do the trick.  Since many (all?) of the superseeker transforms treat 
sequence elements as integers written in decimal, this would seem to be a 
good idea, because it's implicitly applying a rebasing into decimal already!

In fact, this would tend to suggest a new keyword "string"(?) to be used to 
flag those sequences whose elements are exotic encodings not naturally 
interpretable as integers--such as the "Look and Say" sequence, A005150 
(BTW a fitting number for this wacky sequence, since "51-50" is police code 
for "lunatic"!<;-)

So... Should we "officially adopt" this rebasing idea?  Is this notation 
OK?  Please let me know your thoughts and suggestions.

Thanks!