4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Tim Ratigan Dec 5 '13 at 5:44
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Did you mean $\lceil \log_b(n+1)\rceil=k$ in the very final equality? $\endgroup$ – jII Dec 5 '13 at 6:01
  • $\begingroup$ @jesterII: I did indeed; thanks! $\endgroup$ – Brian M. Scott Dec 5 '13 at 6:06
  • $\begingroup$ 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'? $\endgroup$ – jII Dec 5 '13 at 6:18
  • $\begingroup$ @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 ... $\endgroup$ – Brian M. Scott Dec 5 '13 at 6:24
  • $\begingroup$ ... 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$. $\endgroup$ – Brian M. Scott Dec 5 '13 at 6:25
1
$\begingroup$

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:

Start with the Kronecker delta:

$$\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)}$$

The computation of the digits of a number 'a' in base 'b' can be done in a computable integer sequence, in that we already know the exact length of the sequence which is of course the number of digits in total. The expression for this computation is:

$$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=ceil($log_B(N+1)$)". If you can demonstrate this part, then I think that effectively serves as proof for what you are asking.

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