Most Significant Digit but without Calculator

Question

Consider set $S = \{2^0, 2^1, 2^2, 2^3, 2^4, 2^5, \dots, 2^{2003}, 2^{2004}\}$ and $\log2 = 0.3010$. Find the number of elements in the set $S$ whose most significant digit is 4.

It is also known that the most significant digit of $2^{2004}$ is 1 and consists of 604 digits.

I'm interested in an answer that solves it without the use of scientific calculators.

Someone solved it using the below method but it went over my head:

1 1 1 1 1

2 2 2 3 3

4 4 5 6 7

8 9

Above pattern is followed in powers of as 2^0 = 1, 2^1 = 2, 2^2 = 4, 2^3 = 8, 2^4 = 16, 2^5 = 32, 2^6 = 64, 2^7 = 128, 2^8 = 256, 2^9 = 512.

Let X be the number of groups that show the pattern of 4 and let Y be the number of groups that show the pattern of 3. Since MSD (most significant digit) of 2^2004 is 1 and contains 604 digits so 2^2003 will the largest number of the set with 603 digits.

Now, X + Y = 603 4X + 3Y = 2004 so X = 195

So, the answer is 195.

I know that the answer 195 is correct but how? The above solution provided to me contains a lot of technicality like how do we know that powers of 2 has MSD as 7 and 9 too and what is the deal with the X and Y thing that ultimately leads us to the answer?

Answer 1

To expand on how the solution you included in your question works: Consider the powers of $2$ with $k$ digits. There are five possible sequences of first digits of these $k$-digit powers of $2$:

• $1 \to 2 \to 4 \to 8$. For instance, for $k = 1$ digit, we have $2^0 = \boldsymbol{1}$, $2^1 = \boldsymbol{2}$, $2^2 = \boldsymbol{4}$, and $2^3 = \boldsymbol{8}$.
• $1 \to 2 \to 4 \to 9$. For instance, for $k = 16$ digits, we have $2^{50} = \boldsymbol{1}125899906842624$, $2^{51} = \boldsymbol{2}251799813685248$, $2^{52} = \boldsymbol{4}503599627370496,$ and $2^{53} = \boldsymbol{9}007199254740992$.
• $1 \to 2 \to 5$. For instance, for $k = 3$ digits, we have $2^7 = \boldsymbol{1}28$, $2^8 = \boldsymbol{2}56$, and $2^9 = \boldsymbol{5}12$.
• $1 \to 3 \to 6$. For instance, for $k = 2$ digits, we have $2^4 = \boldsymbol{1}6$, $2^5 = \boldsymbol{3}2$, and $2^6 = \boldsymbol{6}4$.
• $1 \to 3 \to 7$. For instance, for $k = 14$ digits, we have $2^{44} = \boldsymbol{1}7592186044416$, $2^{45} = \boldsymbol{3}5184372088832$, and $2^{46} = \boldsymbol{7}0368744177664$.

For every number length ranging from $k = 1$ digit through $k = 603$ digits, we must see one of those five patterns. This covers all of $S$ except $2^{2004}$, which begins with a $1$.

Let $x$ be the number of patterns of length $4$ (the first two) and $y$ be the number of patterns of length $3$ (the last three). Then from the fact that there are $603$ different number lengths under consideration, we have

$$ x+y = 603 $$

From the fact that there are $2004$ powers of $2$ under consideration, and knowing that $x$ patterns are of length $4$ and $y$ patterns of length $3$, we have

$$ 4x+3y = 2004 $$

Solving these yields $x = 195$ and $y = 408$. Since the patterns of length $4$ are exactly those that contain a power of $2$ with the first digit $4$, the number of such powers of $2$ is $x = 195$.

---

The above solution does not use the value of the log (base $10$) of $2$. Here's one way to use it: First, imagine that the log of $2$ was exactly $0.3$. Then the log of $2^2 = 4$ would be $0.6$, that of $2^3 = 8$ would be $0.9$, and so forth. The log of $10/2 = 5$ would be $1-0.3 = 0.7$. So a power of $2$ would begin with $4$ if its log had a decimal portion of $0.6$.

Since $3$ and $10$ are relatively prime, the log of every $10$ consecutive powers of $2$ would contain each of the decimal portions from $0.0$ through $0.9$ exactly once each, meaning that they would contain $0.6$ exactly once, meaning in turn that exactly one of those $10$ powers of $2$ would begin with $4$. These would be $2^2, 2^{12}, 2^{22}, \ldots, 2^{2002}, \ldots$ and the answer to our question would be $201$.

But the log of $2$ is not exactly $0.3$. A closer approximation is $0.301$. Suppose that were exact; then the log of $4$ would be $0.602$, and that of $5$ would be $1-0.301 = 0.699$. Since $301$ and $1000$ are relatively prime, the logs of every $1000$ consecutive powers of $2$ would contain each decimal portion from $0.000$ through $0.999$ exactly once each, meaning in particular that it would contain a decimal portion between $0.602$ and $0.698$ (inclusive) exactly once each, meaning in turn that there would be $698-602+1 = 97$ powers of $2$ that began with $4$. Along with $2^{2002}$, the answer to our question would be $97+97+1 = 195$.

That turns out to be the answer, but to be sure, we'd have to know the log of $2$ to more digits. Five digits is a good place to stop; the log of $2$ to five digits is $0.30103$, and that is very accurate. (The value to ten digits is $0.3010299957$.) With that value, and a bit more algebra, we can confirm the answer of $195$.

Answer 2

The leading digits of powers of an integer greater than $1$ will follow Benford's law quite closely (especially in the long run).

According to Benford's law, for appropriate data sets, the proportion of items with leading digit $4$ should be (very close to) $\log \left(\frac{5}{4}\right)$ (base ten logarithm being used here).

You can get approximations for $\log (4)$ and $\log(5)$ from the given approximation for $\log(2)$. And from that you can get a good approximation for $\log \left(\frac{5}{4}\right)=\log(5)-\log(4)$.

This will lead you to a value that is very close to the actual answer (which I (cheatingly) checked with Python)...the error is less than $1$ (i.e., the value you get will round up or down to the exact answer).

Calculator not needed if you're willing to do the necessary arithmetic by hand.

Answer 3

We have $\log 4=2 \log 2 \approx 0.602$ and $\log 5 = \log 10 - \log 2 \approx 0.699$. From Benford's law we expect about $0.699-0.602=0.097$ of the numbers to start with $4$, so we need to compute $0.097 \cdot 2004 =(0.100-0.003)2004=200.4-6.0=194.4$ as a guess.

To tell if a number has leading digit $4$ you look at the decimal part of the base $10$ logarithm. If it is between $0.602$ and $0.699$ the leading digit will be $4$. The logs of the powers of $2^n$ will be reasonably evenly distributed because they are just $0.301n$