# Proving number of digits d to represent integer n in base B?

I am interested in learning about proofs for discrete mathematics. One recurring fact I find in the literature is that

the number of digits $d$ required to represent integer $N$ in base $B$ is $\log_B{n}$

I am unhappy with this on two fronts. The first is that no source I have come across actually proves this claim. The second, I do not think the claim is true, and I am trying to prove this in a few ways but am finding slightly different results.

If we have a $d$ digit string in base $B$, this is an element of the set $\{0,1,\dots,B-1\}^{d}$ which has $B^d$ elements. This means we can represent exactly $0,1,\dots,B^{d}-1$ using $d$ digits; solving for $N$ gives $d=\lceil \log_B{(N+1)}\rceil$.

An alternative way to see this is that the largest integer we can represent is $\sum_{i=0}^{d-1}(B-1)*B^i$, which is also $B^d-1$ and gives the same result.

Why then, do sources describe this as $\log_B(n)$? An alternative representation that is equally confusing is $\lfloor\log_BN\rfloor+1$; this requires a proof that $$\lfloor\log_BN\rfloor+1 = \lceil \log_B{(N+1)}\rceil$$

which I cannot seem to resolve; unless I am on the wrong track entirely.

-
It's easier to think about some numerical examples before generalizing. What is the rule for base $10$? I know $\lfloor\log_{10}376\rfloor=2$. $\lfloor \log_{10}10^n\rfloor=n$, even though $10^n$ has $n+1$ digits. You're right, though, that $\log_B n$ is totally wrong, at least in the sense that it's usually not an integer. – Tim Ratigan Dec 5 '13 at 5:44

Since $\log_bn$ is an integer if and only if $n$ is a power of $b$, it’s clear that the number of digits is generally not exactly $\log_bn$; it is, however, closely approximated by $\log_bn$ and grows (with $n$) like $\log_bn$, which is what is generally meant by that assertion.

To get the exact number of digits of the base $b$ representation of $n$, where $n$ is a positive integer, observe that $n$ has $k$ digits if and only if $b^{k-1}\le n<b^k$, since $b^k$ is the smallest integer to have $k+1$ digits. This is equivalent to the inequality $k-1\le\log_bn<k$, i.e., to $\lfloor\log_bn\rfloor=k-1$, or $k=\lfloor\log_bn\rfloor+1$.

To use the ceiling function instead, add $1$ to each term of the inequality $b^{k-1}\le n<b^k$ to get $b^{k-1}<n+1\le b^k$; this is possible because we’re dealing here only with integers, so that $b^{k-1}\le n$ is precisely equivalent to $b^{k-1}<n+1$, and similarly for the other inequality. But $b^{k-1}<n+1\le b^k$ says exactly that $k-1<\log_b(n+1)\le k$ and hence that $\lceil\log_b(n+1)\rceil=k$.

-
Did you mean $\lceil \log_b(n+1)\rceil=k$ in the very final equality? – jesterII Dec 5 '13 at 6:01
@jesterII: I did indeed; thanks! – Brian M. Scott Dec 5 '13 at 6:06
This is an interesting way of looking at things, but let's consider the very edge case when $n=0$. This may be a theoretical question; the floor tells us we require an undefined number of bits (I see you specified that $n$ is a positive integer), whereas the ceiling says we need 1 bit. Perhaps this is unrelated, however, in that the implicit question is 'do we need bits to represent no bits'? – jesterII Dec 5 '13 at 6:18
@jesterII: That’s not really an edge case: it’s a completely separate problem, since the powers of $b$ scale is no longer applicable. If we decide, in accordance with common usage, that ‘$0$’ is the standard representation, then $1$ digit is required. The floor formula says, honestly, that it doesn’t apply to the case $n=0$ and so forces us to recognize that $0$ is a special case. The ceiling formula just happens, more or less by accident, to give the right result; this makes it possible to overlook the fact that its derivation doesn’t actually justify applying it to $n=0$. The floor ... – Brian M. Scott Dec 5 '13 at 6:24
... version is nicer; I think that the main reason that people sometimes use the ceiling version is the coincidence that it happens to work for $n=0$. – Brian M. Scott Dec 5 '13 at 6:25