In mathematics, the logarithm is the inverse function to exponentiation. That means the logarithm of a given number x is the exponent to which another fixed number, the base b, must be raised, to produce that number x. In the simplest case, the logarithm counts the number of occurrences of the same factor in repeated multiplication

AMC 10A 2014 Problem 25 (or 12A Problem 22) is a curious case of estimation gymnastics.

There are several treatments of this problem (search it online if you are into reading ‘solutions’). We will work through sequential hints as usual. Try the problem on your own instead of reading ‘solutions’.

Reading ‘solutions’ in Ipad is bad on two counts. Its bad for your eyes and your brain.”

– Sir Issac Newton

Problem

The number \( 5^{867} \) is between \( 2^{2013} \) and \( 2^{2014} \). How many pairs of integers (m, n) are there such that \( 1 \leq m \leq 2012 \) and $$ 5^n < 2^m < 2^{m+2} < 5^{n+1} $$ ?

Key Ideas you will need to solve this problem

  • Logarithm

Also see

Advanced Math Olympiad Program


Hint 1: \( log_2 5 \sim 2.33 \)

This is actually very good estimate. Notice that $$ 2^2 < 5 < 2^{2 + \frac{1}{3}} = 2^{\frac{7}{3}}  $$

How do we know this is true? It bears mark of a well established method of creating log tables since Napier’s time. Raise both sides to the power 3 and check if all is well. That is whether the following is true: $$ (2^2)^3 < 5^3 < (2^{\frac{7}{3}})^3 = 2^7 $$

This is not only true, \( 5^3 =125 \) is very close to \( 2^7 = 128 \)

Hence \( log_2 5 \sim \frac{7}{3} \sim 2.33 \)

Hint 2: Logarithm is a monotonically increasing function

In other words, ‘taking log on all sides’ is a perfectly good way of preserving inequality. Hence take logarithm base 2 to have $$ n \cdot \log_2 5 < m < m+2 < (n+1) \cdot \log_2 5 $$

The left hand side inequality yields $$ 2.33n < m $$

The right hand piece yields $$ m+2 < 2.33 (n+1 ) = 2.33n + 2.33 \Rightarrow m < 2.33n + 0.33 $$

Combining these two we have $$ 2.33n < m < 2.33n + 0.33 $$

Hint 3: Integer in-between

2.33n and 2.33n + 0.33 are dangerously close! In order to squeeze a nice and round integer in between (that is m) we will need to be careful.

We really want the fractional part of 2.33n to be 0.67 or more. This works whenever n is a multiple of 3 from n= 1 to 33. (Check rigorously for n = 3k +2 and n= 3k+1, fractional part of 2.33n is not large enough. So adding 0.33 won’t make 2.33n and 2.33n + 0.33 jump across an integer).

Each time we multiply by a greater number, the fractional part recedes by > 0.01. Hence by the time it is n = 30, it has receded enough to make room for the next power (3k+1 or 31)

The process repeats from next nine numbers of the form 3k+1 (31, 34, 37, 40, 43, 46, 49, 52, 55, 58) and then we slide over to 3k+2 and so on.

Hint 4: Some of these 288 cases won’t work.

Not all multiples of 3 are born equal. Ehm…

We want $$ \log _2 5 \cdot n < m <  \log_2 5 \cdot n + (\log_2 5 – 2) $$

That is \( \log_2 5^n < m < \log_2 \frac{5^{n+1}}{4} \)

Here is the observation: If I is an integer and I < x < x + t < I + 1 then 2x + t

Other useful link