0
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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