Short notation of combination of numbers

Question

To calculate how many unique combination there are for the numbers 1 till 150,000,000 I use this formula:

$\frac{1}{2}(150,000,000 \cdot (1 + 150,000,000)) \approx 11.3 \cdot 10^{15}$

In a software program that I am developing, I want to use a short notation to store certain combinations (to save space). The combinations to be stored change continuously, so obviously I am not searching a way to store "fixed combinations" but a way to transform a certain combination to a short "code".

A way to do this is to use alphanumeric characters (A-Z, a-z, 0-9) which gives me 62 possible values per character. $62 ^ 9 \approx 13.5 \cdot 10^{15}$ so I am able to store any combination of (1-150,000,000) by using max 9 characters, which is great.

HOWEVER .... How can I reverse the alphanumeric code (e.g. Abz7N) back to the the actual combination of numbers ? Looping through the $\approx 13.5 * 10^{15}$ possibilities is extremely inefficient ... Is there a more efficient way ?

Answer 1

Well $50^5 = 312,500,000$, which is twice what you need for each number. That means a $5$ digit number in base $50$ can store each number in your pair, with a leading digit no larger than (the digit standing for) $25$. So with $10$ characters from your $50$ letter alphabet you can store both numbers and tell them apart - $5$ digits each. No need to count the pairs.

There are clean algorithms for base conversion that are implemented in most languages, so that code is essentially written for you.

But is that really necessary? Does it really save space? $150,000,000$ is just under $2^{28}$, so needs four bytes of storage - maybe more, depending on how your language manages integers. That's the same order of magnitude as the $5$ bytes it would take to store the characters in the solution above. Are you sure you shouldn't just create an appropriate list (or hash table or whatever) of pairs of numbers and let the language do its thing? If you encapsulate this in a class with access methods you can start with this naive implementation and optimize later if you need to (and if you can).