Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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}$.

share|improve this question

1 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.

share|improve this answer
    
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
2  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.