5
$\begingroup$

I'm trying to map a 12 digit number into a fixed width file. For a number of reasons, it must be compressed in such a way that it is guaranteed to be less than or equal to 9 characters (alpha numeric is fine). My first thought was a change of base, but I can't find an equation which gives an upper bound the number of characters needed for a given base.

For example, transforming into base 32

123456789101 -> 3IV9I6JD

Which is 8 digits. How to find a basis which is guaranteed to need 9 or less characters to represent a 12 digits number?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Hint: what is the biggest $n$ digit number in base $b$? $\endgroup$ – Tom van der Zanden Jun 25 '15 at 16:24
  • $\begingroup$ use base-64 instead of base-32 $\endgroup$ – phuclv May 27 '18 at 9:28
11
$\begingroup$

The largest 12 digit number in base 10 is $10^{12} - 1$. In general the largest $n$ position number in a base $b$ is $b^{n} - 1$. So in your case you need a base large enough that $b^{9} - 1 > 999,999,999,999$ $(10^{12} - 1).$ Solving for $b$:

$$b^{9} - 1 > 10^{12} - 1$$ $$b^{9} > 10^{12}$$ $$b^{9/9} > 10^{12/9}$$ $$b > 10^{12/9}$$ $$b > \sqrt[9]{10^{12}}$$ $$b > 21.54$$

So make your base 22 and your numeric data will fit in 9 positions.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ you can simplify your fourth step to b>10^(4/3) which would then simplify the fifth step. I would also note that bases which are larger will still work like base 26 (all letters), base 36 (all letters and numbers) or (my favorite) base 33 (all numbers and all letters except for o,l,i to reduce transcription errors) and leave room for growth. $\endgroup$ – hildred Jun 25 '15 at 22:50
  • 1
    $\begingroup$ But changing to base 32 or base 64 is much easier than non-power-of-2 bases. The OP can always pad zeros to the beginning of the number to make it 9 $\endgroup$ – phuclv Jun 26 '15 at 5:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.