Base i-1: There Be Dragons

John Baez recently posted this picture (by Anton Sherwood) on his G+ stream:
The story behind it is pretty cool, and it involves two of my favorite things: TAOCP and unusual number systems.
Let’s start with an odd looking piece of MATLAB code.

function s = dragon(x)
    t  = i-1;
    r = t.^(0:31);
    b = dec2bin(x);
    b = b(end:-1:1) - '0';
    v = b .* r(1:numel(b));
    s = sum(v);

This takes an integer and returns a complex number. It does that by summing powers of i-1. Which powers? The ones which correspond to the 1 bits in the binary form of the input. In other words, if we pass in 5 (which is 2^3 + 2^1), it returns (i-1)^3 + (i-1)^1.
Let’s try plugging a few values in:

As you can see, the values are sort of spiraling out around the complex plane, but in an odd, herky-jerky way. Let’s take a closer look at the pattern.
If we plot the first 50 values like this:

n = 50;
xy = zeros(1,n);
for idx=1:n
    xy(idx) = dragon(idx);
end
plot(xy);
text(real(xy),imag(xy),num2str((1:n)'));
axis square

We get the following picture.

This pattern has an extremely interesting property. It will eventually visit every Gaussian integer! This means that it can be used to map any Gaussian integer to a positive real integer!
But what is that pattern? If you clicked on the link to Anton’s image, you might have recognized the shape. What he did is color each pixel using the integer that maps to it. Something like this:

w = 640;
cdata = zeros(w);
for idx=1:1000000
    v = dragon(idx);
    r = real(v) + w/2;
    c = imag(v) + w/2;
    if (r >= 1 && r <= w && c >= 1 && c <= w)
        cdata(r,c) = idx;
    end
end
image(cdata,'CDataMapping','scaled');

The result looks like this:

Do you recognize our old friend the dragon curve? Where’d that come from?