12
$\begingroup$

Is there a direct way to determine how many digits a power of 2 will contain without actually performing the multiplication?

An estimation would help as well if there is no absolute solution.

EDIT: In both decimal and binary bases.

  • 0
    In what base???2012-08-02
  • 7
    Chaz, when no base is specified, what could we possible assume but base 10?2012-08-02
  • 3
    *Q.* [How do you explain the concept of logarithm to a five year old?](http://math.stackexchange.com/q/129013/856) *A.* [Roughly speaking, a logarithm is like the the number of digits in a decimal number.](http://math.stackexchange.com/a/129023/856) Ergo, Américo's answer. :)2012-08-02
  • 1
    Regarding the Edit, the number of digits (bits, really) of a power of 2 in binary basis is, well... computable.2012-08-02
  • 0
    As it was asked, in base 2 we will find that $2^n$ has $n$ bits.2012-08-02
  • 2
    @Ross: As indicated in my comment (except one needs $n+1$ bits).2012-08-02

4 Answers 4

23

If you solve for $x$ the equation $$2^{n}=10^{x}$$ you get the exponent of $10$ $$x=\frac{n\ln 2}{ \ln 10}\approx 0.30103n\qquad \text{(see comment)}$$

Answer to the edit. In binary base since

$$2^{n}=1\cdot 2^{n}+0\cdot 2^{n-1}+\cdots +0\cdot 2^{2}+0\cdot 2^{1}+0\cdot 2^{0},$$

we have $n+1$ bits

$$\left( 2^{n}\right) _{2}=\underset{n+1\text{ bits}}{\underbrace{1\overset{n\text{ 0's}}{\overbrace{0\ldots 000}}}}.$$

Comment. The number $x$ is never an integer because $2^{n}$ can only terminate in $2,4,6$ or $8$. So, as commented by Random832, the number of digits in decimal base is

$$\left\lfloor 1+\frac{n\ln 2}{\ln 10}\right\rfloor =1+\left\lfloor n\,\log _{10}2\right\rfloor ,$$

which is the sequence A034887 in OEIS (Gost's comment).

  • 1
    I'd have gone to $\lfloor n\frac{\ln 2}{\ln 10}+1\rfloor$, to get directly to a _number of digits_. Using floor(x+1) rather than ceil to take into account the case where the base is [a power of] 2, not strictly necessary for base 10.2012-08-02
  • 0
    @Random832 Thanks! I've added your formula as a comment.2012-08-02
  • 1
    It's also [sequence A034887 in OEIS](http://oeis.org/A034887)2012-08-02
  • 0
    @Ghost Thanks! I've added your information to the answer.2012-08-03
14

There's an estimate of great use in computer science: $2^{10k} \approx 10^{3k}. $ In particular it's always just a bit bigger, so $2^{10}$ has four digits, $2^{20}$ has seven, and so on. I'm not sure how to find cutoffs for lengths not a multiple of 3.

  • 0
    Good point for estimation.2012-08-02
1

I'm not sure if there is a proof for this, but there is a repeating pattern that seems to hold true for as large as I can verify.

As mentioned in another answer, a $2^{10}$ step increases the base 10 number by three digits.

It seems within each $2^{10}$ there is a pattern where each base 10 digit will increment on each of these powers of two: $2^{4} \cdot 2^{3} \cdot 2^{3}$.

One could make a pretty efficient function to compute the number of digits using this pattern. Again, not sure how long this pattern holds true for, but the number is pretty large.

  • 1
    *a $2^{10}$ step increases the base 10 number by three digits*... Often, but not always.2012-08-03
  • 0
    @did Yea, there is no rigor behind that comment. Haha. Although I'm curious, can you show me a counter-example?2012-08-03
  • 0
    For every $n$ such that $(10^3/2^{10})\cdot10^k\lt2^n\lt10^k$ for some $k$, the step increases by **four** digits. And there are infinitely such $n$ by ergodicity.2012-08-03
0

IntegerPart(log(x)+1) where x is some equation will give the number of digits on the left hand side of the decimal. It's what I use anyway :)