For integers $n \ge 0$ and $k \ge 2$, the following are equivalent:
- How many digits are in the bijective base-k numeral for n?
- If all the words on an alphabet of size $k$ are listed in shortlex order, how many letters are in the $n$th word?
The formula $$\lfloor log_k( (n+1)(k-1) )\rfloor \quad (k \ge 2, \ n \ge 0) $$ is mentioned in the bijective numeration article. Is this correct? If so, how to prove it?
The smallest integer of length $\ell$ is $$\underbrace{111\ldots 111}_{\ell}=\sum_{j=0}^{\ell-1}k^j=\frac{k^\ell-1}{k-1}\;.$$ Thus, $n$ requires $\ell$ digits if and only if
$$\frac{k^\ell-1}{k-1}\le n<\frac{k^{\ell+1}-1}{k-1}\;,\tag{1}$$
or $k^\ell\le(k-1)n+1<k^{\ell+1}$. Taking logs base $k$ yields the inequality
$$\ell\le\log_k\big((k-1)n+1\big)<\ell+1\;,$$
which is of course equivalent to $$\ell=\left\lfloor\log_k\big((k-1)n+1\big)\right\rfloor\;.\tag{2}$$
However, taking advantage of the fact that $n$ is an integer, we can also observe that as $n$ runs over the set $$\left\{\frac{k^\ell-1}{k-1},\ldots,\frac{k^{\ell+1}-1}{k-1}-1\right\}$$ of integers of length $\ell$, $(k-1)n$ runs over the set of multiples of $k-1$ between $k^\ell-1$ and $k^{\ell+1}-k$ inclusive, and therefore $(k-1)(n+1)$ runs over the set of multiples of $k-1$ between $k^\ell+k-2$ and $k^{\ell+1}-1$ inclusive. These are precisely the multiples $(k-1)m$ of $k-1$ that satisfy $k^\ell\le(k-1)m<k^{\ell+1}$ and hence $\ell\le\log_k(k-1)(n+1)<\ell+1$, so $(2)$ is indeed equivalent to
$$\ell=\left\lfloor\log_k\big((k-1)(n+1)\big)\right\rfloor\;.$$