Why does this work? What is the best exponent to approximate the logarithm?

Question

Suppose i want to get a upper bound of $log_53$ without other tools than elementary algebra.

I can do this:

Let $x = log_53$, then $5^x=3$

I raise both sides to $4$, then: $(5^x)^4 = 3^4$ And since $3^4 < 5^3$ it follows that $5^{4x} < 5^3$, then $x < \frac{3}{4}$

However, if i raise both sides to $13$ is equal to: $(5^x)^{13} = 3^{13}$ And since $3^{13} < 5^9$ it follows that $5^{13x} < 5^9$, then $x < \frac{9}{13}$

In this case with exponent $13$ the approximation is better.

So, with different exponent i can get different upper bounds. Similarly, the same can be done with the lower bound.

And my question is,

Given $log_ab = x$, what is the best exponent $m$ such that $(a^x)^m = b^m$ gives the better approximation for both cases?(Lower and upper bounds)

Answer 1

There's no "best exponent", because you can always get better and better exponents, but you can use continued fractions to do this systematically. With continued fractions, we will write $x$ in the form $$ x = a_0 + \cfrac1{a_1 + \cfrac1{a_2 + \cfrac1{a_3 + \cfrac1{a_4 + \dots}}}}. $$ where $a_0, a_1, a_2, a_3, a_4, \dots$ is an infinite sequence of natural numbers.

We can truncate this sequence at any point, getting upper or lower bounds depending on where we stop. (If you stop at an even $a_k$, you get a lower bound; if you stop at an odd $a_k$, you get an upper bound.)

We compute the sequence iteratively: $a_0$ is $\lfloor x\rfloor$ (the greatest integer less than $x$) and to find $a_1$ onward you just replace $x$ by $\frac{1}{x - a_0}$.

---

All this is abstract and general, so here is how it will go in your example.

Let $x = \log_5(3)$. Then we can estimate that $0 < x < 1$ (because $5^0 < 3 < 5^1$) so $a_0 = \lfloor \log_5(3)\rfloor = 0$, and we will keep going with $\frac1{\log_5(3)} = \log_3(5)$.

We can estimate that $1 < \log_3(5) < 2$, because $3^1 < 5 < 3^2$, so $a_1 = \lfloor \log_3(5)\rfloor = 1$, and we will keep going with $\frac{1}{\log_3(5)-1} = \frac1{\log_3(5/3)} = \log_{5/3}(3)$.

We can estimate that $2 < \log_{5/3}(3) < 3$, because $(\frac53)^2 < 3 < (\frac53)^3$ (this expands to $25 < 27$ but $81 < 125$), so $a_2 = \lfloor \log_{5/3}(3) \rfloor = 2$, and we will keep going with $\frac1{\log_{5/3}(3) - 2} = \frac1{\log_{5/3}(27/25)} = \log_{27/25}(\frac53)$.

We could estimate that $6 < \log_{27/25}(\frac53) < 7$, because $(\frac{27}{25})^6 < \frac53 < (\frac{27}{25})^7$, but this has gotten tricky to check: it involves checking that $3^{19} < 5^{13}$ but $3^{22} > 5^{15}$. This gives us $a_3 = 6$, but maybe we'd better quit while we're ahead, or get a computer.

At this point, our best lower bound is $$ a_0 + \cfrac1{a_1 + \cfrac1{a_2}} = 0 + \cfrac1{1 + \cfrac12} = \frac23 $$ and our best upper bound is $$ a_0 + \cfrac1{a_1 + \cfrac1{a_2 + \cfrac1{a_3}}} = 0 + \cfrac1{1 + \cfrac1{2 + \cfrac16}} = \frac{13}{19}. $$

Answer 2

The rational number $p/q$ (with $p, q$ positive integers) satisfies $p/q < \log_a b$ iff $p < q \log_a b$ iff $a^p < b^q$, and similarly $p/q > \log_a b$ iff $a^p > b^q$. The best rational approximations of $\log_a b$ (or any irrational number) can be obtained using continued fractions. For example, the continued fraction of $\log_5(3)$ is

$$ \log_5(3) = 1/(2+1/(6+1/(1+1/(1+1/(1+1/(3+\ldots))))))$$

Truncating the continued fraction to a finite number of terms gives you the convergents of the continued fraction. The first few in this case are $$ 0,1,\frac{2}{3},{\frac{13}{19}},{\frac{15}{22}},{\frac{28}{41}},{\frac{43}{63 }}$$ which are alternately lower bounds and upper bounds for $\log_5(3)$.

Answer 3

A much less guessing approach while still staying elementary is to use bisection. Essentially, we can start with $0<\log_5(3)<1$, then we see how $5$ compares to $3^2$ to deduce that $1<2\log_5(3)<2$, then we compare $5^3$ to $3^4$ to deduce that $2<4\log_5(3)<3$, and so on.

A couple of quick approximations can easily be coded this way: example code.