Machin-like formulas for logarithms

Question

I found this math puzzle blog post http://fredrikj.net/blog/2013/03/machin-like-formulas-for-logarithms/ which I'm reposting here with permission. I'm setting this to community wiki to minimize the perception that I'm leeching for internet points, but if this question is somehow inappropriate then I would take the blame and not the original author.

Machin-like formulas express $\pi$ as an integer combination of arctangents evaluated at reciprocals of integers. The most famous is

$$\pi = 16 \arctan \frac{1}{5} - 4 \arctan \frac{1}{239}$$

which historically has been used for many record computations of $\pi$, including Machin’s own accomplishment of breaking the 100-digit barrier in 1706. (Nowadays the more efficient Chudnovsky algorithm is usually used, but Machin-like formulas still hold up quite well.)

For a Machin-like formula

$$\pi = \sum_{i=1}^N A_i \arctan \frac{1}{B_i}$$

one can define its efficiency as

$$e = \sum_{i=1}^N \frac{1}{\log B_i}.$$

A smaller $e$ roughly corresponds to a shorter computation time. Larger $B_i$ give faster convergence of each arctangent series, but formulas with larger $B_i$ usually involve more terms, so there is a tradeoff.

By considering hyperbolic arctangents, one can obtain rapidly converging representations for logarithms of integers. For example, here is a simple Machin-like formula for $\log 2$ (it’s easy to find others):

$$\log 2 = 2 \operatorname{arctanh} \frac{1}{5} + 2 \operatorname{arctanh} \frac{1}{7}.$$

Having efficient formulas of this kind for the logarithms of small integers is very useful in some applications.

I recently noticed by accident (while looking at the output from a quick brute force search for Machin-like formulas with PSLQ in mpmath) that there is a set of particularly efficient Machin-like formulas that allow computing $\log 2$, $\log 3$ and $\log 5$ simultaneously from just three hyperbolic arctangents:

$$\log 2 = 14 \operatorname{arctanh}\frac{1}{31} + 10 \operatorname{arctanh}\frac{1}{49} + 6 \operatorname{arctanh}\frac{1}{161}$$

$$\log 3 = 22 \operatorname{arctanh}\frac{1}{31} + 16 \operatorname{arctanh}\frac{1}{49} + 10 \operatorname{arctanh}\frac{1}{161}$$

$$\log 5 = 32 \operatorname{arctanh}\frac{1}{31} + 24 \operatorname{arctanh}\frac{1}{49} + 14 \operatorname{arctanh}\frac{1}{161}$$

This trivially also allows one to compute the logarithm of any integer of the form $2^i 3^j 5^k$.

Here is a challenge: for a positive integer $n$, what is the most efficient set of hyperbolic arctangents that gives you the logarithms of all integers up to $n$ (or equivalently just the primes up to $n$) simultaneously? Can you find a more efficient set for $n = 5$?

Note that if $n$ gets large and we already have a basis for the integers up to $n-1$, we can just add

$$\log(n) = \log(n-1) + 2 \operatorname{arctanh} \frac{1}{2n-1},$$

so it might be enough to consider smallish $n$.

Note that for $x \gt 1, \text{ arctanh}\frac{1}{x} = \frac{1}{2} (\log (x+1) - \log (x-1)).$ So, it makes sense to consider denominators $x$ so that $x-1$ and $x+1$ are smooth, which explains the denominators of $31$, $49$, and $161$ above. Also, the following system is not as good

$$\begin{eqnarray}\log 2 &=& 2 \text{ arctanh} \frac{1}{5} + 2 \text{ arctanh} \frac{1}{7} \newline \log 3 & = & 4 \text{ arctanh} \frac{1}{5} + 2 \text{ arctanh} \frac{1}{7} \newline \log 5 &=& 4 \text{ arctanh} \frac{1}{5} + 4 \text{ arctanh} \frac{1}{7} + 2 \text{ arctanh} \frac{1}{9} \end{eqnarray}$$

since we want larger denominators instead of smaller so that we can compute $\operatorname{arctanh} \frac{1}{b}$ more rapidly. A measure of the cost of computing $\sum a_i \operatorname{arctanh} \frac{1}{b_i}$ is $\sum \frac{1}{\log b_i}$.

Answer 1

The "efficiency" of the set of denominators $\lbrace 31, 49, 161 \rbrace$ is $0.744$. It is better to use $\lbrace 251, 449, 4801, 8749\rbrace$, which lets you compute the logs of the first $4$ primes for an efficiency of $0.573$. Those are the largest numbers I could find which are sandwiched between $7$-smooth numbers. Using the first $5$, $6$, or $7$ primes didn't improve this, as they resulted in slightly larger efficiencies, e.g. $0.601$ for $\lbrace 28799,57121,62425,74359,246401,388961,672281 \rbrace$, the $7$ largest numbers I could find so that adding or subtracting $1$ produces a $17$-smooth number.

$$\begin{eqnarray} \operatorname{arctanh}\frac{1}{251} &=& \frac{1}{2}(\log 2 + 2 \log 3 - 3 \log 5 + \log 7) \newline \operatorname{arctanh}\frac{1}{449} &=& \frac{1}{2}(-5\log 2 + 2 \log 3 + 2 \log 5 - \log 7) \newline \operatorname{arctanh}\frac{1}{4801} &=& \frac{1}{2}(-5\log 2 -\log 3 - 2\log 5 + 4 \log 7) \newline \operatorname{arctanh}\frac{1}{8749} &=& \frac{1}{2}(-\log 2 -7\log 3+4\log 5+\log 7). \end{eqnarray}$$

By inverting this system we get

$$\begin{eqnarray}\log 2 &=& 144~a(251) + 54~a(449)-38~a(4801)+62~a(8749) \newline \log3&=& 228~a(251)+86~a(449)-60~a(4801)+98~a(8749) \newline\log5 &=& 334~a(251) + 126~a(449)-88~a(4801)+144~a(8749) \newline \log 7 &=& 404~a(251)+152~a(449)-106~a(4801)+174~a(8749) \end{eqnarray}$$

where $a(n) = \operatorname{arctanh}\frac{1}{n}$.

It is plausible that it would be better to use a small set of primes, but not the smallest ones.

Answer 2

One can generate these formulas systematically using the method described in Arndt's book (as already mentioned by meij in a comment).

I have tabulated what I believe are the best possible n-term formulas for the first n primes up to n = 25, along with the analogous formulas for primitive arctangents up to n = 22: see Table 1 and Table 2 in https://arxiv.org/abs/2207.02501

These are the first 7 sets of denominators:

{3}

{7, 17}

{31, 49, 161}

{251, 449, 4801, 8749}

{351, 1079, 4801, 8749, 19601}

{1574, 4801, 8749, 13311, 21295, 246401}

{8749, 21295, 24751, 28799, 74359, 388961, 672281}

And for the first 25 primes:

{373632043520429, 386624124661501, 473599589105798, 478877529936961, 523367485875499, 543267330048757, 666173153712219, 1433006524150291, 1447605165402271, 1744315135589377, 1796745215731101, 1814660314218751, 2236100361188849, 2767427997467797, 2838712971108351, 3729784979457601, 4573663454608289, 9747977591754401, 11305332448031249, 17431549081705001, 21866103101518721, 34903240221563713, 99913980938200001, 332110803172167361, 19182937474703818751}

The algorithm here is just to start with the largest candidate denominator (the list is finite) and keep adding denominators that preserve linear independence of the exponents vectors. I believe (but have not tried to prove) that this results in the lowest possible Lehmer measure.

Note that for example the 7-term set {28799, 57121, 62425, 74359, 246401, 388961, 672281} mentioned by Douglas Zare does not work because there is a linear dependence: acoth(57121) - acoth(62425) - acoth(672281) = 0.