Sum of number of digits in 2 numbers

Question

I am trying to solve the following without using logarithms.

Find the sum of the total number of digits in each of $2^{2006}$ and $5^{2006}$

My attempt:

I know that $d(a\times b)$ for positive integers $a$ and $b$ is one of:

• $d(a) + d(b)$
• $d(a) + d(b) - 1$

As $d(2^{2006} \times 5^{2006}) = d(10^{2006}) = 2007$ this means that $d(2^{2006}) + d(5^{2006})$ is either $2007$ or $2008$.

I cannot figure out a way to outrule one of these possibilities. Please help, and thank you in advance.

Answer 1

Let $a_n$ be the number of digits in $2^n$ and $b_n$ be the number of digits in $5^n$.

Prove by induction that $a_n + b_n = n+1$.

Hints towards a solution:

• Check that base case of $n = 1$.
• Clearly $ a_n \leq a_{n+1} \leq a_n + 1 $ and $ b_n \leq b_{n+1} \leq b_n + 1$.
• If $ a_{n+1} + b_{n+1} > (n+1) + 1$, then it is equal to $ n+3$ and we must have $a_n < a_{n+1}, b_n < b_{n+1}$. How does this lead to a contradiction? Hint: $2^n \times 5^n = 10^n$.

$2^n < 10^{a_{n+1} } < 2^{n+1}, 5^n < 10 ^{b_{n+1} } < 5^{n+1}$.
Multiplying both chains of inequalities, we get $10^n < 10^{a_{n+1} + b_{n+1} } < 10^{n+1}$.
But there is no integer between $n$ and $n+1$.

• Likewise, if $a_{n+1} + b_{n+1} < (n+1)+1$, then it is equal to $n+1$. Find a similar contradiction.

---

Note: This is a logarithm proof in disguise, as it boils down to $ \log_{10} 2 + \log_{10} 5 = 1$.

Answer 2

If a has n digits, and b has m digits, then ab has either n+m or n+m-1 digits. It has n+m digits if and only if (a / 10^n) (b / 10^m) >= 0.1.

In this case ab = 10^2006; since 2^2006 and 5^2006 are not a 1 followed by zeroes the scaled product is 0.1, and n+m = 2007.

Answer 3

I have edited my answer to remove the whiff of logarithms.

Any positive integer greater than $~1~$ has a unique prime factorization.

This means that it is impossible to find positive integers $~n,m~$ such that either:

• $2^n = 10^m.$

• $5^n = 10^m.$

Therefore, for any positive integer $~n~$, there must exist non-negative integers $~m_1, m_2,~$ such that

• $10^{m_1} < 2^n < 10^{m_1 + 1}.$
• $10^{m_2} < 5^n < 10^{m_2 + 1}.$

This implies that

$$10^{m_1 + m_2} < 2^n \times 5^n = 10^n < 10^{m_1 + m_2 + 2}.$$

This implies that

$$m_1 + m_2 < n < m_1 + m_2 + 2.$$

However, $~m_1, m_2, ~$ and $~n~$ are integers.

Therefore, you must have that $~n = m_1 + m_2 + 1.$

---

Further, you have that for any positive integer $~k,~$ and any non-negative integer $~a,$
if $~10^a \leq k < 10^{a+1},~$ then $~k~$ has $(a+1)$ digits.

So, you can now conclude that :

• $~2^n~$ has $~(m_1 + 1)~$ digits.

• $~5^n~$ has $~(m_2 + 1)~$ digits.

Therefore, the sum of the number of digits of $~2^n~$ and the number of digits of $~5^n~$ must equal
$(m_1 + 1) + (m_2 + 1) = n+1.$

Answer 4

Rather ugly, but avoids logarithms (even in disguise, I think, unless the disguise has fooled me):
We will show that $d(2^n)+d(5^n) = n+1$. First, write the two in this form $$2^n = a10^m+b$$and $$5^n = c10^l+d$$ where all variables are non-negative integers, $0 < a,c \le 9$, $b<10^m$ and $d<10^l$. Clearly, $2^n < 10^{m+1}$ and $5^n < 10^{n+1}$, so $10^n < 10^{m+l+2}$ Also, we have $10^n> 10^{m+l}$, thus, $10^n = 10^{m+l+1}$. Which means $$10^{m+l+1} = ac10^{m+l} + bc10^l + ad10^m + bd$$ This gives: $ac<10$. (There is an intuitive way to understand this too, just consider the leading digits of $2^n$ and $5^n$).

---

Now, list out a few powers of $2$ and $5$. You will observe that if $d(2^{n+1}) = d(2^n)$ then $d(5^{n+1}) = d(5^n)+1$ and if $d(2^{n+1}) = d(2^n)+1$ then $d(5^{n+1}) = d(5^n)$. Here's a proof:

Case 1 (if $d(2^{n+1}) = d(2^n)$ then $d(5^{n+1}) = d(5^n)+1$):
Since $d(2^{n+1}) = d(2^n)$, we get that $a < 5$. So, $c \ge 2$. Hence, $5(c10^l+d) > 10^{l+1}$ or $d(5^{n+1}) = d(5^n)+1$.

Case 2 (if $d(2^{n+1}) = d(2^n)+1$ then $d(5^{n+1}) = d(5^n)$):
Since $d(2^{n+1}) = d(2^n)+1$, we get $2(a10^m+b) > 10^{m+1}$ so $a \ge 5$. Thus, $c = 1$ and we get $5(c10^l+d) < 10^{l+1}$ so $d(5^{n+1}) = d(5^n)$.

The result follows from these two cases, and the final answer is $\boxed{2007}$.

Answer 5

Here's another way to show that $d(2^n) + d(5^n) = n+1$. As you established in your question, we know that $d(2^n \times 5^n) = n+1$, and therefore $d(2^n) + d(5^n) = n+1$ or $n+2$.

Let $N = (2^n-1)(5^n-1)$.

Note that since neither $2^n$ nor $5^n$ have a last (units) digit of $0$, it must be true that $d(2^n-1) = d(2^n)$ and $d(5^n-1) = d(5^n)$, so that

$$d(2^n) + d(5^n) = d(2^n-1) + d(5^n-1)$$

But $d(N) < d(2^n \times 5^n)$ as $10^n$ is the smallest number with $n+1$ digits, so $d(N) \le n$.

This means that, applying the same idea you mentioned,

$$d(2^n-1) + d(5^n-1) \le n+1$$

Thus the only possibility is that

$$d(2^n) + d(5^n) = d(2^n-1) + d(5^n-1) = n+1$$