# 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? – jII 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'? – jII 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

This is what I use for this calculation, supposing a to be in it's base 10 representation, and we wish to determine the digits of it's base b representation, we can compute this as follows:

$$\delta \left( x,y \right) =\cases{1&x=y\cr 0&x\neq y\cr}\quad\qquad\quad\qquad\quad\qquad\quad\qquad\quad\qquad\quad\qquad\quad\qquad\quad\quad\quad\quad\quad\quad\quad\text{ (1)}$$
$$d_{{n}} \left( a,b \right) =\sum _{k=1}^{ \Bigl\lfloor {\frac { \ln \left( a \right) }{\ln \left( b \right) }}\Bigr\rfloor +1} \left( \delta \left( n,k \right) -b\delta \left( n,k+1 \right) \right) \Bigl\lfloor{a{b}^{k- {\Bigl\lfloor\frac {\ln \left( a\right) }{\ln \left( b \right) }\Bigr\rfloor} -1}} \Bigr\rfloor \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad$$
For example, $$a=12345$$ in base $$b=10:$$ will, evaluate to the arithmetic progression with initial value of 1 and d=1 of length 5: $$\left\{ d_{{1}} \left( 12345,10 \right) ,d_{{2}} \left( 12345,10 \right) ,d_{{3}} \left( 12345,10 \right) ,d_{{4}} \left( 12345,10 \right) ,d_{{5}} \left( 12345,10 \right) \right\} = \left\{ 1,2,3,4, 5 \right\}$$
As far as proof that the number of digits that are needed to represent a number in another base, say b=2, the value $$\Bigl\lfloor\frac {\ln \left( n\right) }{\ln \left( b \right) }\Bigr\rfloor+1$$ is the same thing as the floor of $$\log_B(n) +1$$.So whatever resource simply stated $$\log_B(n)$$ is wrong. But I am unclear as to what you mean by the statement "Solving for N gives $$d=\operatorname{ceil}(\log_B(N+1))$$". If you can demonstrate this part, then I think that effectively serves as proof for what you are asking.