# Factoring a number to get an encoded string

Say we encode the string $BCA$ in the following way: \begin{align*}BCA &= 2 \times 26^2 + 3 \times 26^1 + 1 \times 26^0 \\ &= 1456 \end{align*} Is it possible to get back to the string $BCA$, given only the number $1456$?

-

Yes, it is possible as Mark has shown you one way to get the string digits from the least significant (that is getting $A$ first then $C$ and then $B$ finally).

But you have to be careful in using this method of encoding, because you are using base $26$, the number could be large if you are dealing with say strings of length $10$.

Another way to get back the strings is by calculating

$$\left \lfloor log_{26} 1432 \right \rfloor = 2$$

This tells you that the highest power of $26$ is $2$.

Start dividing by $26^2$ to get the most significant digit, i.e.

$$\left \lfloor \frac{1431}{26^2} \right \rfloor = 2 \tag{1}$$

and from $(1)$ you know that most significant digit is $B$. The remaining number is

$$1431 - 2 \times 26^2 = 1431 - 1352 = 79$$

To find the next significant digit

$$\left \lfloor log_{26} 79 \right \rfloor = 1$$

and

$$79 = \bf{3} \times 26 + \bf{1}$$

Therefore you get the digits from the most significant to least as $B$, $C$ and $A$.

-

Yes. (But note that 1456 is not correct; $2\cdot26^2 + 3\cdot26 + 1 = 1431$, not $1456$.)

First, divide your number, 1431, by 26, giving quotient, 55, and a remainder, 1. The remainder of 1 means that the last letter is A.

Now divide the quotient 55 by 26, giving a quotient of 2 and a remainder of 3. The remainder, 3, says that the next-to-last letter is C.

Finally, divide the quotient 2 by 26, giving a quotient of 0 and a remainder of 2. This says that the next previous letter is B.

Now the quotient is 0, so we are done.

-
I think this works better than KV Raman's method because A is taken to be 1 instead of 0. So for example $26^2$ actually gets interpreted as $25 \times 26 + 26$. This method is able to take care of that nicely as long as we understand that if the remainder is 0 then the last letter is 26. – Wonder May 8 '12 at 14:12
@Wonder: Gosh, I completely overlooked that! Thanks. – MJD May 8 '12 at 14:13
Decoding algorithms in general has to work both ways (left to right or right to left). Instead of re-inventing a new algorithm one could also use Base-32. (stackoverflow.com/questions/641361/base32-decoding) – Kirthi Raman May 10 '12 at 2:45