Problem #449

Machin Like Formulae
Public 12/01/17 10xp Programming 100.0%

One of the most famous formulae for computing $\pi$ is
$ \frac{\pi}{4} = 4.\arctan(\frac{1}{5})-\arctan(\frac{1}{239}) $ due to John Machin (1706) who used it to compute 100 decimal places.

We can rewrite it as:
$\arctan(1/239) = -\arctan(1/1) + 4.\arctan(1/5)$

It turns out that many integers like 239 have an inverse which can be decomposed as a linear combination of Arctan of inverses.

A few examples:
$ \arctan(\frac{1}{3}) = \arctan(1)-\arctan(\frac{1}{2} )$
$ \arctan(\frac{1}{7}) = - \arctan(1)+2.\arctan(\frac{1}{2} )$
$ \arctan(\frac{1}{8}) = \arctan(1)-\arctan(\frac{1}{2} )-\arctan(1/5)$
$ \arctan(\frac{1}{13}) = \arctan(1)-\arctan(\frac{1}{2} )-\arctan(1/4)$
$ \arctan(\frac{1}{17}) = -\arctan(1)+2.\arctan(\frac{1}{2} )-\arctan(1/12)$
$ \arctan(\frac{1}{18}) = \arctan(1)-2.\arctan(\frac{1}{2})+\arctan(1/5)$
$ \arctan(\frac{1}{21}) = \arctan(1/4)-\arctan(1/5)$
$ \arctan(\frac{1}{30}) = \arctan(1)-\arctan(\frac{1}{2} )-\arctan(1/4)-\arctan(1/23)$
$ \arctan(\frac{1}{31}) = \arctan(1/5)-\arctan(1/6)$
$ \arctan(\frac{1}{32}) = -\arctan(1)+2.\arctan(\frac{1}{2} )-\arctan(1/9)$

The irreductible numbers, those which cannot be decomposed this way are called Störmer numbers.
Thus, the inverse of every number which is not a Störmer number can be expressed as a linear combinaison of Arctan of inverse of smaller irreductible integers.

What makes John Machin's formula particularily efficient is the fact that it contains few terms and the numbers involved are not too small: the convergence of the Arctan serie is then quite fast.

Let's define the cost of a formula as the sum of the inverse of the distinct integers without 1.
$ C(32) = \frac{1}{2} + \frac{1}{9} + \frac{1}{32} = 0.642361 $

Numbers like 21 or 31 are not suitable for a computation of $\pi$ as they do not include the number 1 in their decomposition, their cost will be infinity.

What are the 10 most efficient numbers less than 20000?

Answer format: Comma separated list in ascending order of cost.

Example: 41,46,75,17,32,7,68,93,43,57 (for numbers less than 100)

$ C(41) = 0.6077235772 \rightarrow \arctan(\frac{1}{41}) = \arctan(1) - 2.\arctan(\frac{1}{2}) + 2.\arctan(\frac{1}{12})$
$ C(46) = 0.6421095008 \rightarrow \arctan(\frac{1}{46}) = - \arctan(1) + 2.\arctan(\frac{1}{2}) - \arctan(\frac{1}{12}) - \arctan(\frac{1}{27})$
$ C(75) = 0.6421212121 \rightarrow \arctan(\frac{1}{75}) = - \arctan(1) + 2.\arctan(\frac{1}{2}) - \arctan(\frac{1}{12}) - \arctan(\frac{1}{22})$
$ C(17) = 0.6421568627 \rightarrow \arctan(\frac{1}{17}) = - \arctan(1) + 2.\arctan(\frac{1}{2}) - \arctan(\frac{1}{12})$
$ C(32) = 0.6423611111 \rightarrow \arctan(\frac{1}{32}) = - \arctan(1) + 2.\arctan(\frac{1}{2}) - \arctan(\frac{1}{9})$
$ C( 7) = 0.6428571429 \rightarrow \arctan(\frac{1}{ 7}) = - \arctan(1) + 2.\arctan(\frac{1}{2})$
$ C(68) = 0.6813725490 \rightarrow \arctan(\frac{1}{68}) = 2.\arctan(1) - 3.\arctan(\frac{1}{2}) - \arctan(\frac{1}{6})$
$ C(93) = 0.6899193548 \rightarrow \arctan(\frac{1}{93}) = \arctan(1) - 2.\arctan(\frac{1}{2}) + \arctan(\frac{1}{6}) - \arctan(\frac{1}{80})$
$ C(43) = 0.6899224806 \rightarrow \arctan(\frac{1}{43}) = \arctan(1) - 2.\arctan(\frac{1}{2}) + \arctan(\frac{1}{6})$ $ C(57) = 0.7175438596 \rightarrow \arctan(\frac{1}{57}) =-2.\arctan(1) + 3.\arctan(\frac{1}{2}) + \arctan(\frac{1}{5})$

[My timing : < 10 sec]



You need to be a member to keep track of your progress.
Register


Time may end, but hope will last forever.

Other Challenge Sites

Contact

elasolova
[64][103][109][97][105][108][46][99][111][109]