How to evaluate $\log x$ to high precision "by hand"

Question

I want to prove

$$\log 2<\frac{253}{365}.$$

This evaluates to $0.693147\ldots<0.693151\ldots$, so it checks out. (The source of this otherwise obscure numerical problem is in the verification of the Birthday problem.) If you had to do the calculation by hand, what method or series would you use to minimize the number of operations and/or size of the arguments involved in order to get this result? I'm doing a formal computer proof, so it's not exactly by hand, but I still want to minimize the number of evaluations needed to get to this result.

One method is by rewriting it into $2<e^{253/365}$ and using the power series; since it is a positive series you know you can stop once you have exceeded $2$. Working this out, it seems you need the terms $n=0,\dots,7$ of the sum, and then it works out to

$$2<\sum_{n=0}^7\frac{(253/365)^n}{n!}=\frac{724987549742673918011}{362492763907870312500},$$

which involves rather larger numbers than I'd like. There is also the limit $(1+\frac{253}{365n})^n\to$ $e^{253/365}$, but the convergence on this is not so good; it doesn't get past $2$ until $n=68551$, at which point we are talking about numbers with $507162$ digits.

For $\log 2$ there is of course the terribly converging alternate series $\log 2=\sum_{n=1}^\infty\frac{-(-1)^n}n$, which requires $71339$ terms to get the desired bound. This can be improved by pushing the series into its geometrically convergent region as $\log 2=2\log{\sqrt 2}=-2\sum_{n=1}^\infty \frac{(1-\sqrt2)^n}n$, but now there is the added complication of estimating $\sqrt 2$ to sufficient precision. Assuming that $\sqrt 2$ is known exactly, you need to take this series out to $12$ terms, at which point we are verifying

$$\frac{1959675656 \sqrt2-2771399891}{1011780}<0\Leftarrow2771399891^2>1959675656^2\cdot 2.$$

What other methods are there to do a calculation like this? Is there a way to use a root-finding method like Newton's to get a strict bound out with fast convergence?

Answer 1

You could express this as $\log(1/2) > -\dfrac{253}{365}$. The series $$\log(1/2) = \log(1-1/2) = -\sum_{n=1}^\infty \dfrac{1}{n 2^n}$$ converges quickly, and has nice bounds: $$ \log(1/2) \ge - \sum_{n=1}^{N-1} \dfrac{1}{n 2^n} - \sum_{n=N}^\infty \dfrac{1}{N 2^n} = - \sum_{n=1}^{N-1} \dfrac{1}{n 2^n} - \dfrac{1}{N 2^{N-1}}$$

EDIT: Another way to write it is $2 < (\exp(1/365))^{253}$, and use the continued fraction $$ \exp(1/n) = 1 + \dfrac{1}{n-1 + \dfrac{1}{1 + \dfrac{1}{1 + \dfrac{1}{3n-1 + \dfrac{1}{1+ \dfrac{1}{1+ \dfrac{1}{5n-1 + \ldots}}}}}}}$$ In particular, $$\exp(1/365) >1+ 1/(364+1/(1+1/(1+1/1094))) = \dfrac{800080}{797891}$$ and (if you don't mind exact arithmetic with big integers) $$\left(\dfrac{800080}{797891}\right)^{253} > 2$$

Answer 2

Since $\log 2=2\operatorname{arctanh}\frac{1}{3}$, we may use the series: $$ \log 2 = \sum_{n\geq 0}\frac{2}{(2n+1)\,3^{2n+1}} $$ and the bound: $$ \sum_{n\geq 4}\frac{2}{(2n+1)\,3^{2n+1}}\leq\sum_{n\geq 4}\frac{2}{3^{2n+3}}=\frac{1}{157464} $$ to prove that (we just need the terms of the previous series till $n=4$): $$ \log 2\approx \frac{4297606}{6200145} = \color{red}{0.69314}\color{blue}{60474\ldots}$$ where the red digits are the right ones for sure.

Answer 3

We may use this generalized continued fraction to get directly excellent fractions as near as wished of $\,\ln\,2$ : $$\ln\,2=\cfrac 1{1+\cfrac 1{2+\cfrac 1{3+\cfrac 2{2+\cfrac 2{5+\cfrac 3{2+\cfrac 3{7+\cfrac 4{2+\cfrac 4{9+\cdots}}}}}}}}}=b_0+\cfrac {a_1}{b_1+\cfrac {a_2}{b_2+\cfrac {a_3}{b_3+\cfrac {a_4}{\cdots}}}}$$

Let's obtain the first successive convergent using the previous values of $a_k,b_k$ and $\;\left[\matrix {n_k\\d_k}\right]=\left[\matrix {n_{k-1}\;n_{k-2}\\d_{k-1}\;d_{k-2}}\right]\left[\matrix {b_k\\a_k}\right],\quad\left[\matrix {n_1\\d_1}\right]=\left[\matrix {b_0\,b_1+a_1\\b_1}\right]=\left[\matrix {1\\1}\right],\;\left[\matrix {n_0\\d_0}\right]=\left[\matrix {b_0\\1}\right]=\left[\matrix {0\\1}\right]$ :

\begin{array} {l|c|ccccc} k&b_k,a_k&&&f_k=\dfrac{n_k}{d_k}\\ \hline\\ 1 & \color{#0000ff}{1,1} &\cfrac 1{1}&&=\cfrac 1{1}=\dfrac {n_1}{d_1}\\ 2 & \color{#0000ff}{2,1} & \cfrac 1{1+\frac 1{2}}&=\dfrac{n_1 b_2+n_0 a_2}{d_1 b_2+d_0 a_2}=\dfrac{1\cdot\color{#0000ff}{2}+0\cdot\color{#0000ff}{1}}{1\cdot\color{#0000ff}{2}+1\cdot\color{#0000ff}{1}}&=\dfrac 23=\dfrac {n_2}{d_2}\\ 3 & \color{#0000ff}{3,1} & \cfrac 1{1+\frac 1{2+\frac 1{3}}}&=\dfrac{n_2 b_3+n_1 a_3}{d_2 b_3+d_1 a_3}=\dfrac{2\cdot\color{#0000ff}{3}+1\cdot\color{#0000ff}{1}}{3\cdot\color{#0000ff}{3}+1\cdot\color{#0000ff}{1}}&=\dfrac {7}{10}=\dfrac {n_3}{d_3}\\ 4 & \color{#0000ff}{2,2} &\cfrac 1{1+\frac 1{2+\frac 1{3+\frac 2{2}}}}&=\dfrac{7\cdot\color{#0000ff}{2}+2\cdot\color{#0000ff}{2}}{10\cdot\color{#0000ff}{2}+3\cdot\color{#0000ff}{2}}&=\dfrac {18}{26}=\dfrac {9}{13}\\ 5 & \color{#0000ff}{5,2}&\cfrac 1{1+\frac 1{2+\frac 1{3+\frac 2{2+\frac 2{5}}}}}&=\dfrac{18\cdot\color{#0000ff}{5}+7\cdot\color{#0000ff}{2}}{26\cdot\color{#0000ff}{5}+10\cdot\color{#0000ff}{2}}&=\dfrac {104}{150}=\dfrac {52}{75}\\ 6 & \color{#0000ff}{2,3}&\cfrac 1{1+\frac 1{2+\frac 1{3+\frac 2{2+\frac 2{5+\frac 3{2}}}}}}&=\dfrac{104\cdot\color{#0000ff}{2}+18\cdot\color{#0000ff}{3}}{150\cdot\color{#0000ff}{2}+26\cdot\color{#0000ff}{3}}&=\dfrac {262}{378}=\dfrac {131}{189}\\ 7 & \color{#0000ff}{7,3}&\cfrac 1{1+\frac 1{2+\frac 1{3+\frac 2{2+\frac 2{5+\frac 3{2+\frac 3{7}}}}}}}&=\dfrac{262\cdot\color{#0000ff}{7}+104\cdot\color{#0000ff}{3}}{378\cdot\color{#0000ff}{7}+150\cdot\color{#0000ff}{3}}&=\dfrac {2146}{3096}=\dfrac {1073}{1548}\\ 8 & \color{#0000ff}{2,4}&\cfrac 1{1+\frac 1{2+\frac 1{3+\frac 2{2+\frac 2{5+\frac 3{2+\frac 3{7+\frac 4{2}}}}}}}}&=\dfrac{2146\cdot\color{#0000ff}{2}+262\cdot\color{#0000ff}{4}}{3096\cdot\color{#0000ff}{2}+378\cdot\color{#0000ff}{4}}&=\dfrac {5340}{7704}=\dfrac {445}{642}\\ 9 & \color{#0000ff}{9,4}&\cfrac 1{1+\frac 1{2+\frac 1{3+\frac 2{2+\frac 2{5+\frac 3{2+\frac 3{7+\frac 4{2+\frac 4{9}}}}}}}}}&=\dfrac{5340\cdot\color{#0000ff}{9}+2146\cdot\color{#0000ff}{4}}{7704\cdot\color{#0000ff}{9}+3096\cdot\color{#0000ff}{4}}&=\dfrac {56644}{81720}=\dfrac {14161}{20430}\\ \cdots &\\ \end{array}

For even values of $k$ the fraction will be too small while for odd values it will be too large. The last fraction provided here (for $k$ odd) is larger than $\,\ln\,2\,$ but smaller than your fraction proving your claim. The previous approximation is smaller than $\,\ln\,2\,$ (but more precise too than your fraction).

As observed earlier a convergent from the continued fraction of the numerical approximation $\,0.69315\;$ returns directly the initial fraction : $$\ln(2)\approx 0.69315\approx\cfrac 1{1+\cfrac 1{2+\cfrac 1{3+\cfrac 1{1+\cfrac 1{6+\cfrac 1{3+\cfrac 11}}}}}}=\frac {253}{365}$$

Answer 4

$\log 2 = \log (1 + 1/3) + \log (1 + 1/2)$, and each of those terms can be easily evaluated to the desired predictions using $\log (1+x) = x - x^2/2 + x^3/3 - \cdots$. There are other ways to write $\log 2$ as a sum of logarithms that will let you write it as a sum of more, but faster-converging series; I'm not sure what minimizes the arithmetic. In general we have

$$ \log 2 = \log \left( 1 + {1 \over 2n-1} \right) + \log \left( 1 + {1 \over 2n-2} \right) + \cdots + \log \left(1 + {1 \over n} \right)$$

of which the original identity I gave is the $n = 2$ case.