Converting to and from a number system that doesn't have a zero digit

Question

Consider Microsoft Excel's column-numbering system. Columns are "numbered" A, B, C, ... , Y, Z, AA, AB, AC, ... where A is 1.

The column system is similar to the base-10 numbering system that we're familiar with in that when any digit has its maximum value and is incremented, its value is set to the lowest possible digit value and the digit to its left is incremented, or a new digit is added at the minimum value. The difference is that there isn't a digit that represents zero in the letter numbering system. So if the "digit alphabet" contained ABC or 123, we could count like this:

(base 3 with zeros added for comparison)

base 3 no 0    base 3 with 0    base 10 with 0
-----------    -------------    --------------
  -      -            0               0
  A      1            1               1
  B      2            2               2
  C      3           10               3
 AA     11           11               4
 AB     12           12               5
 AC     13           20               6
 BA     21           21               7
 BB     22           22               8
 BC     23          100               9
 CA     31          101              10
 CB     32          102              11
 CC     33          110              12
AAA    111          111              13

Converting from the zeroless system to our base 10 system is fairly simple; it's still a matter of multiplying the power of that space by the value in that space and adding it to the total. So in the case of AAA with the alphabet ABC, it's equivalent to (1*3^2) + (1*3^1) + (1*3^0) = 9 + 3 + 1 = 13.

I'm having trouble converting inversely, though. With a zero-based system, you can use a greedy algorithm moving from largest to smallest digit and grabbing whatever fits. This will not work for a zeroless system, however. For example, converting the base-10 number 10 to the base-3 zeroless system: Though 9 (the third digit slot: 3^2) would fit into 10, this would leave no possible configuration of the final two digits since their minimum values are 1*3^1 = 3 and 1*3^0 = 1 respectively.

Realistically, my digit alphabet will contain A-Z, so I'm looking for a quick, generalized conversion method that can do this without trial and error or counting up from zero.

Edit

The accepted answer by n.m. is primarily a string-manipulation-based solution. For a purely mathematical solution see kennytm's links:

• What is the algorithm to convert an Excel Column Letter into its Number?
• How to convert a column number (eg. 127) into an excel column (eg. AA)

Answer 1

Convert to base-3-with-zeroes first (digits 0AB), and from there, convert to base-3-without-zeroes (ABC), using these string substitutions:

   A0  =>  0C
   B0  =>  AC
   C0  =>  BC

Each substitution either removes a zero, or pushes one to the left. In the end, discard leading zeroes.

It is also possible, as an optimisation, to process longer strings of zeros at once:

A000...000 = 0BBB...BBC
B000...000 = ABBB...BBC
C000...000 = BBBB...BBC

Generalizable to any base.