Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

1 Answer

up vote 2 down vote accepted

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

share|improve this answer
    
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
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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