10
$\begingroup$

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

$\endgroup$

2 Answers 2

7
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ You mention that you are looking for numbers "sandwiched between smooth numbers." What is the importance of smooth numbers for this problem? $\endgroup$ Mar 27, 2013 at 3:05
  • $\begingroup$ $\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$. $\endgroup$ Mar 27, 2013 at 3:17
  • 2
    $\begingroup$ relevant oeis oeis.org/A175607 in particular section 32.4 of jjj.de/fxt/fxtbook.pdf "Simultaneous computation of logarithms of small primes" $\endgroup$
    – meij
    Mar 27, 2013 at 17:10
  • $\begingroup$ 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. $\endgroup$ Mar 27, 2013 at 19:59
  • $\begingroup$ 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! $\endgroup$ Mar 28, 2013 at 18:13
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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