# How do I efficiently budget for digits when converting from one base to another?

I'm trying to work out a formula that gives me the minimum number of digits required to express a number in a target radix (r2) knowing only the source radix (r1) and number of significant digits (d).

I've been messing around with this for quite some time but I think I've figured out that the formula is:

$\left\lfloor \log_{r2}(r1) × d\right\rfloor + 1$

My question is, did I get this right? It works for a variety of examples, but I know that doesn't necessarily mean it's correct. I lack the skills to prove it. I didn't study advanced math. Please go easy on me.

Let $r_1, r_2 > 1$ be the two bases, then the smallest number requiring $n+1$ digits in base $r_1$ is $r_1^n$ which has representation $10\ldots 0$ (where we have $n$ zeros), therefore an arbitrary number $m$ needs $n+1$ digits if and only if $$r_1^n \le m < r_1^{n+1}$$ and this relation holds in any base. Also for the same $m$ we have $$r_2^{n \cdot \log_{r_2} r_1} \le m < r_2^{(n+1) \cdot \log_{r_2} r_1}.$$ So the number of digits needed to represent $m$ in base $r_2$ is contained between $\lfloor n\log_{r_2} r_1 \rfloor + 1, \ldots, \lceil (n+1)\log_{r_2} r_1 \rceil + 1$. So your formula is indeed a good approximation and some times it is right. For example consider $r_1 = 2, r_2 = 3$, and: $$\begin{array}{l|l|l|l|c|c} m & r_1 & r_2 & d_2 & d_3 & \lfloor (d_2-1)\cdot \log_3 2 \rfloor + 1 & \lceil d_2\cdot \log_3 2\rceil + 1 \\ \hline 0 & 0 & 0 & 1 & 1 & 1 & 2 \\ 1 & 1 & 1 & 1 & 1 & 1 & 2 \\ 2 & 10 & 2 & 2 & 1 & 1 & 3 \\ 3 & 11 & 10 & 2 & 2 & 1 & 3 \\ 4 & 100 & 11 & 3 & 2 & 2 & 3 \\ 5 & 101 & 12 & 3 & 2 & 2 & 3 \\ 6 & 110 & 100 & 3 & 3 & 2 & 3 \\ 7 & 111 & 101 & 3 & 3 & 2 & 3 \\ \end{array}$$ As you can see in the table, for $m = 3$ the number of digits needed in base $3$ is strictly between the bounds, for $m \in \{0,1,2,4,5\}$ the lower bound is assumed, and for $m \in \{ 6,7 \}$ the upper bound is assumed.