# How many digits are in the bijective base-k numeral for n?

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?

Computed cases appear to confirm the formula $$\lceil log_k( (n+1)(k-1) )\rceil \quad (k \ge 2, \ n \ge 0)$$

which 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\;.$$