Representing numbers by quasilexicographic ordered strings, formula for size of conversion between different alphabets

Question

Let $X_r = \{ 0, 1, \ldots, r-1 \}$ and $X_b = \{ 0, 1, \ldots, b-1 \}$ be two finite alphabets with order's given by their numerical value. Consider the quasilexicographic (or shortlex) order on $X_r^*$ and $X_b^*$. Then we have standard bijection's $\operatorname{r-string} : \mathbb N \to X_r^*$ and $\operatorname{b-string} : \mathbb N \to X_b^*$ given by for example with $r = 2$ and $X_r = \{ 0, 1 \}$: $$ \begin{array}{r|l} n & \operatorname{2-string}(n) \\ \hline 0 & \varepsilon \\ 1 & 0 \\ 2 & 1 \\ 3 & 00 \\ 4 & 01 \\ 5 & 10 \\ 6 & 11 \\ 7 & 000 \\ 8 & 001 \end{array} $$ and so on. Now consider the following translation function $\operatorname{trans}_{~b, r} : X_r^* \to X_b^*$ between these representations of natural numbers given by $$ \operatorname{trans}_{~b, r} := \operatorname{b-string} \circ ~\operatorname{r-string}^{-1}. $$ How to prove that $$ |\operatorname{trans}_{~b,r}(u)| = \lceil |u| \cdot \log_b r \rceil $$ for all $u \in X_r^*$ where $|u|$ denotes the length of a string $u$?

Answer 1

It’s false as written. Take $b=10$, $r=2$, and $u=111$: $\operatorname{2-string}^{-1}(u)=14$, $\operatorname{10-string}(14)=13$, and $|\operatorname{trans}_{10,2}(111)|=2$, but $\lceil|u|\cdot\log_{10}2\rceil=\lceil3\log_{10}2\rceil=\lceil\log_{10}8\rceil=1$.