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?

up vote 2 down vote accepted

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

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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