Proving the Number of Digits in a Number Formula: A Scientific Exploration

[Buri]

I was playing around with my calculator and I noticed that to calculate the number of digits in a number n we have # of digits in n = [log(n) + 1], where log is in base 10 and [] represents the floor function. I after looked this up and it seems like its true. But how would you go about proving something like this? I thought of writing n as its decimal expansion, and then taking the logarithm, but it doesn't seem to get me no where. Any ideas?

 

[micromass]

Let x be a number, then it is easy to see that

x has n digits if and only if 10^{n-1}\leq x<10^{n}.

If we apply your expression on this, then we obtain

n=\log(10^{n-1})+1\leq \log(x)+1<\log(10^n)+1=n+1

This yields that [\log(x)+1]=n.

 

[HallsofIvy]

A number, n, has "d" digits if and only if 10^{d-1}\le n< 10^d. Take the logarithm (base 10) of each part of that, using the fact that logarithm is an increasing function.

 

[Buri]

Ahhh didn't think of that. Thanks a lot to both of you! :)

 

[Robert1986]

Ahhh didn't think of that. Thanks a lot to both of you! :)

Note that this can be generalized to any base b system. In particular, the number of bits needed to represent a number in base 2 is the log of that number to the base 2. This is really important in the analysis of algorithms.

 

[Buri]

Note that this can be generalized to any base b system. In particular, the number of bits needed to represent a number in base 2 is the log of that number to the base 2. This is really important in the analysis of algorithms.

Funny how you actually mentioned algorithms. I actually got into this problem by looking at the efficiency of the Euclidean Algorithm. I was trying to show that when the Euclidean Algorithm is applied to a and b (a > b) that it terminates in at most 7 times the number of digits of b.