Number of Digits to Represent Integer in Given Number Base

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $n \in \Z_{>0}$ be a (strictly) positive integer.

Let $b \in \Z$ be an integer such that $b > 1$.

Let $d$ denote the number of digits of $n$ when represented in base $b$.


Then:

$d = \ceiling {\map {\log_b} {n + 1} }$

where $\ceiling {\, \cdot \,}$ denotes the ceiling function.


Proof

Let $n$ have $d$ digits.

Then:

\(\displaystyle b^{d - 1}\) \(\le\) \(\, \displaystyle n \, \) \(\, \displaystyle <\, \) \(\displaystyle b^d\) Basis Representation Theorem
\(\displaystyle \leadsto \ \ \) \(\displaystyle b^{d - 1}\) \(<\) \(\, \displaystyle n + 1 \, \) \(\, \displaystyle \le\, \) \(\displaystyle b^d\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle d - 1\) \(<\) \(\, \displaystyle \map {\log_b} {n + 1} \, \) \(\, \displaystyle \le\, \) \(\displaystyle d\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle \) \(\) \(\, \displaystyle \ceiling {\map {\log_b} {n + 1} } \, \) \(\, \displaystyle =\, \) \(\displaystyle d\) Integer equals Ceiling iff Number between Integer and One Less

$\blacksquare$