# Machin-like formulas for logarithms

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} &#8211; 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}$.

-

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.

-
You mention that you are looking for numbers "sandwiched between smooth numbers." What is the importance of smooth numbers for this problem? –  Carl Feynman Mar 27 '13 at 3:05
$\operatorname{arctanh}\frac{1}{n} = \frac{1}{2}(\log(n+1)-\log(n-1))$. If $n-1$ and $n+1$ factor into powers of $2$, $3$, and $5$, for example, then we can express $\operatorname{arctanh}\frac{1}{n}$ in terms of $\log2$, $\log3$, and $\log5$. –  Douglas Zare Mar 27 '13 at 3:17
relevant oeis oeis.org/A175607 in particular section 32.4 of jjj.de/fxt/fxtbook.pdf "Simultaneous computation of logarithms of small primes" –  meij Mar 27 '13 at 17:10
That's interesting, and that book tests the idea of considering other sets of primes, using $x^2+1$ to force the primes to be $1 \mod 4$, for example. For the set of $13$ denominators $\lbrace 51744295,...,3222617399\rbrace$ on page 632, however, I get an efficiency of $0.644$, worse than the examples with 4 through 7 primes, so it is slower if you only want to compute $\lbrace \log2, \log3, \log5\rbrace$. The advantage is that you simultaneously compute the logarithms of the next $10$ primes, too. –  Douglas Zare Mar 27 '13 at 19:59
These findings are very interesting (author of the blog here). The 4-term formula is some 10% faster than the 3-term formula in practice, which is not really that much but still quite nice. Getting a longer list of primes is very useful though. I can't believe I missed the section in Joerg's (great) book! –  Fredrik Johansson Mar 28 '13 at 18:13