# A Mundane Exotic Number System

Numeral systems contain a surprising amount of depth. Our familiarity and
monolingualism with the base 10 positional system runs so deep that we tend to
think of numbers as *being* their base 10 representation. Doing this actually
has merit, given the simple algorithms for arithmetic it offers. However, other
representations often provide interesting insights that seem completely opaque
otherwise.

Take base \(2\), for example. The correspondence between sets of things and base \(2\) numbers can be mined for all sorts of interesting gems, given their correspondence with subsets of some set. Also of note is that the rows of Pascal’s triangle sum to powers of two. If this is new to you, it’s tons of fun to puzzle out why and how it’s related to base \(2\).

A more exotic example is the factorial number system, wherein each position represents the multiple of a factorial—as opposed to the normal power of some base. Given that permutations are counted by the factorials, this numeral system provides a really direct enumeration for permutations.

Another system that pops up in surprisingly mundane places is the bijective
numeration. Excel, for example, uses to label its columns with strings of
letters, like `A`

, `AZ`

, `GDJ`

, *etc.* At first blush, this appears to be a
straightforward base \(26\) system, and indeed there’s a very simple APL
expression to convert from column names to their index:

```
(26⊥1+⎕A⍳⊢)¨'A' 'AZ' 'ZZ' 'GDJ'
1 52 702 4846
```

which *feels* like it’s just doing base \(26\). However, the intuitive inverse
expression fails:

```
(⊂⌷⎕A⍨)∘(26⊥⍣¯1⊢)¨1 52 702 4846
B CA BBA HEK
```

There’s actually two issues with the above. We’re off by one in the index into
`⎕A`

,

```
(⊂⌷⎕A⍨)∘(¯1+26⊥⍣¯1⊢)¨1
A
```

however, when `⊥⍣¯1`

decodes into digits with 0, we get `¯1`

indices:

```
(⊂⌷⎕A⍨)∘(¯1+26⊥⍣¯1⊢)¨26
INDEX ERROR
(⊂⌷⎕A⍨)∘(¯1+26⊥⍣¯1⊢)¨26
∧
```

In general, the standard representation in a base-\(k\) positional system has the same representation in the base-\(k\) bijection numeration as long as the former contains no zeroes. In the case when there are zeroes, the bijective system needs to (recursively) borrow from the left, for essentially the same reason that borrowing happens in the pen-and-paper subtraction algorithm.

```
26{⎕A⌷⍨⊂¯1+⍺{
n←⍵+(m×⍺)-0,⍨1↓m←0=⍵ ⍝ Borrow
(∨\0≠n)/n ⍝ Trim leading zeroes
}⍣≡(⍺⊥⍣¯1⊢)⍵}¨1 52 702 4846
A AZ ZZ GDJ
```

While the above is a fully general solution, IMHO, its verbosity leaves a somewhat unsatisfying aftertaste. The borrow algorithm is ubiquitous, so there is likely some more parsimonious expression.

Paul Mansour shares a completely different approach in his article Excel Column Names, which leverages Excel’s maximum column count to enumerate all names and simply index into them. Our algorithm above is probably \(O(\log n)\), so if you were performing this conversion a whole lot, having a cached index likely performs vastly better.

Thanks for reading.