A Method to Reduce the Lehmer Measure in a Multi-Term Machin-Like Formula for π ()
1. Introduction
The Machin-like formulas for π can be represented in the following form [1] [2] [3] [4] [5]
(1)
In many known equations, the values Bj are integers. Among many other formulas for π [3] [4] [5] [6] [7] , the identities of kind (1) involving arctangent function represent a particular interest due to their potential for rapid convergence.
Since the Maclaurin series expansion of the arctangent function is given by
(2)
we can conclude that in order to improve convergence rate the numbers Bj in Equation (1) should be as large as possible by absolute values. Furthermore, the computational efficiency of a given Machin-like formula (1) for π is obviously higher if the number of the terms J is smaller. It should be noted that implementation of the binary splitting algorithm can also be used to accelerate computation of the series (2) (see for example [8]).
Lehmer introduced a measure [1] [2] [9] [10]
(3)
Nowadays, the Equation (3) is known as the Lehmer measure. We take absolute values
since the constants Bj in Equation (1) may generally be negative.
According to Lehmer, the measure (3) shows “amount of labor” that is required for computation of π for some given Machin-like formula. Specifically, the lower Lehmer measure μ indicates the higher computational efficiency of the Machin-like formula (1) for π. For example, the original Machin formula for π [1] [2] [3] [4] [5] [11] [12] [13]
(4)
that was found by English mathematician John Machin in 1706 has the Lehmer measure
. However, the following Machin-like formula for π
(5)
that was discovered by Gauss has the Lehmer measure
[1] [2]. This signifies that the formula (5) is more efficient in computation of π than the formula (4) as its Lehmer measure is smaller. More detailed descriptions and significance of the Lehmer measure (3) in computation of π can be found in literature [10].
Previously we have shown that the following identity [14] (see also [15])
where
,
, can be rearranged as
(6)
where the constant α can be taken as
(7)
for any integer k greater than 1.
Once α is known, the constant β in Equation (6) can be found by using the following equation [14] [15]
(8)
Application of Equation (8) is not optimal since increasing k drastically slows down computation of the constant β. Fortunately, as we have shown in our work [16] the constant β in Equation (6) can be found more efficiently by using a two-step iteration
(9)
with initial values defined as
(10a)
and
(10b)
such that
(10c)
A method, known as the Todd’s process, is commonly used to generate the Machin-like formulas for π [10] (see also [17]). However, this method is not simple and requires tedious and complicated manipulations with large-size matrices based on a set of some prime numbers [10]. Furthermore, it seems that computer-aided algorithms based on Todd’s process still cannot generate the Machin-like formulas for π containing only integer reciprocals with μ below 1. For example, the following Machin-like formula for π containing only integer reciprocals (see [18] and web-links therein)
(11)
has the Lehmer measure
. To the best of our knowledge this is the smallest Lehmer measure ever reported for the Machin-like formulas for π containing only integer reciprocals.
In our previous publication we have proposed a new method that transforms quotients into integer reciprocals in the Machin-like formulas for π [19]. In particular, we have shown how this approach can be used to generate a Machin-like formula for π that can retain without any quotients the Lehmer measure μ below one. As a further development of our work [19] , here we show how to generate the Machin-like formula for π with the Lehmer measure μ less than 1 even at a smaller value of the integer k. As an example we show that for
the corresponding Machin-like formula (22) for π has the Lehmer measure 0.956916. Therefore, this approach may be promising for efficient computation of digits of π.
2. Preliminaries
As an example, we can take
. Substituting this value into Equation (7) we have
Then, using Equations (10a), (10b) and (10c) together with two-step iteration (9), we can find that
Consequently, substituting these values α and β into Equation (6) yields
(12)
We can use Mathematica to verify this two-term Machin-like formula for π in two ways. The first way is to use a built-in algorithm of the Mathematica by equating logically (with == symbols) the left and right sides of Equation (12). The following Mathematica code:
Pi/4==8*ArcTan[1/10]-ArcTan[1758719/147153121]
validates the identity (12) by returning True. Although this code confirms correctness of this identity, it is not clear how the built-in algorithm of Mathematica validates it.
Another way of validation that follows from Equation (1), implies that the real and imaginary parts of the product (detailed description can be found in [11])
must be equal to each other. For example, there is an elementary proof for the original Machin formula (4) for π [20]
Therefore, the following Mathematica code:
coeff=(10+I)^8*(147153121/1758719+I)^-1;
Re[coeff]==Im[coeff]
also validates the Equation (12) by returning True since the real and imaginary parts of the product
are equal to each other. Further, we will use the second way of validation since it is explicit and, therefore, intuitive for understanding.
The Machin-like formula (12) for π contains a quotient in the argument of the second arctangent function. This quotient is undesirable as its large numerator 1758719 increases the argument of the arctangent function that slows down the convergence rate. Moreover, it also contributes for more digits that also slow down the computation when expansion series like (2) for the arctangent function is used. Therefore, it is very desirable to look for the Machin-like formulas for π, where all constants Bj are integers. In order to resolve this problem we proposed a new method based on the following identity (see [19] for derivation)
(13)
Application of the identity (13) has appeared to be very efficient. Consider as an example a remarkable Machin-like formula for π that was found by Wetherfield in 2004 (see [18] and the web-links therein)
(14)
The Lehmer measure of this formula is small
(see definition (3) for computation of μ). However, the arguments in the last two arctangent function arguments are not integer reciprocals and, consequently, practical application of Equation (14) may be questionable. In order to eliminate these two quotients in arctangent function arguments we can use the following identity
leading to
and
Substituting these two arctangent function relations into Equation (14) results in Equation (11).
Consider now how our approach based on identity (13) can be used to eliminate quotients in (14) [19]. Specifically, applying Equation (13) in a sequence first for
and then for
we obtain the following 7-term Machin-like formula for π
(15)
where all arguments are integer reciprocals. The Lehmer’s measure for this equation is
. It seems that Equation (15) is new and first appeared in our recent publication [19].
The Mathematica code below:
coeff=(107+I)^83*(1710+I)^17*(103697+I)^-22*(1256744+I)^-12*
(9140003941+I)^-22*(3158812219818+I)^12*
(167079344092131066905+I)^22;
Re[coeff]==Im[coeff]
validates Equation (15) by returning True.
In 2002, Kanada broke a record by computing more than one trillion decimal digits of π [21] [22] (current record is 62.8 trillion digits of π [23]). He applied the following self-checking pair of the Machin-like formulas
and
with Lehmer’s measures 1.58604 and 1.7799, respectively.
The current record that was achieved by using the Chudnovsky brothers formula [22] is 62.8 trillion digits of π [23]. This record is larger than Kanada’s 20 years old record by a factor ~60. Since this factor is not large, despite relatively high Lehmer’s measures 1.58604 and 1.7799 we may expect that using most modern supercomputer the self-checking pair above can also generate a comparable amount of digits of π. Therefore, the Machin-like formulas with small Lehmer’s measure have a colossal potential and remain competitive in computing digits of π.
Since Lehmer’s measures of Equations (11) and (15) are smaller, their application in computing π is potentially more efficient than the self-checking pair that was used by Kanada. Furthermore, since first three arctangent function terms in both equations are same, it is easier to compare results of computation when Equations (11) and (15) are used as a self-checking pair.
We have shown already that identity (13) can be used in an iterative procedure such that from Equation (12) it follows that (see [19] for derivation)
(16)
As we can see, this formula contains only integer reciprocals. Therefore, the iteration procedure based on Equation (13) can be used as an alternative to the Todd’s process.
The 7-term Machin-like formula (16) for π can be validated by running the following Mathematica code:
(* Define long string *)
longStr=StringJoin["11757386816817535293027775284419412676",
"7991915008537018836932014293678271636885792397"];
coeff=(10+I)^8*(84+I)^-1*(21342+I)^-1*
(991268848+I)^-1*(193018008592515208050+I)^-1*
(197967899896401851763240424238758988350338+I)^-1*
(FromDigits[longStr]+I)^-1;
Re[coeff]==Im[coeff]
The output of this code is True.
Thus, the initial Equation (12) with quotient can be transformed into Equation (16) with help of the identity (13) using an iterative procedure described in our publication [19]. We can also notice that starting from the second arctangent function term each consecutive integer in Equation (16) is larger by absolute value than the previous one by many orders of the magnitude. This signifies that each consecutive arctangent term contributes smaller and smaller amount for the Lehmer measure μ. Consequently, due to rapidly increasing integers this iteration process enable us to generate the Machin-like formula for π with a small Lehmer measure.
3. Derivation
We will attempt to transform the Machin-like formula (12) for π in a form where initial arctangent terms contain arguments of kind 1/10m, where m is a positive integer. Solving the equation
we can rewrite Equation (12) as follows
Applying now the following identity (see also [19])
the Equation (12) can be recast as
(17)
Repeating same procedure again for Equation (17)
we get
(18)
Since the following quotient
is close to 1000, it is reasonable to represent the last arctangent function from Equation (18) as
This leads to
(19)
The following Mathematica code:
coeff=(10+I)^8*(100+I)^-1*(14717070819/28718779+I)^-1;
eq17=Re[coeff]==Im[coeff];
coeff=(10+I)^8*(100+I)^-1*(14717070819/28718779+I)^-1;
eq18=Re[coeff]==Im[coeff];
coeff=(10+I)^8*(100+I)^-1*(1000+I)^-1*
(14717099537779/14001708181+I)^-1;
eq19=Re[coeff]==Im[coeff];
Print[{eq17,eq18,eq19}]
validates Equations (17)-(19) by returning the list {True,True,True}.
We notice that
is a relatively large number. Therefore, its contribution to the Lehmer measure will not be high and further we can apply identity (13). Thus, taking
and substituting it into in identity (13) we can rewrite Equation (19) as
(20)
Now implying that
and substituting it into identity (13), we obtain
(21)
The Mathematica code below validates Equations (20) and (21):
coeff=(10+I)^8*(100+I)^-1*(1000+I)^-2*(20573+I)*
(151387588781630565746/316421763593+I);
eq20=Re[coeff]==Im[coeff];
ceff=(10+I)^8*(100+I)^-1*(1000+I)^-2*(20573+I)*
(478436082+I)*(14485856968022096352676282153/
10266919376+I);
eq21=Re[coeff]==Im[coeff];
Print[{eq20,eq21}]
by returning the list {True,True}.
Repeating same procedure over and over again, we end up with the following 21-term Machin-like formula for π
(22)
where integer in the last term consists of 600593 digits.
It is not difficult to show that Equation (22) can be represented in a more compact form as
where
such that by iteration
We ceased iteration at 18th step since the number
is not a quotient but an integer (see [19] showing how iteration is implemented).
The following Mathematica code:
Clear[B]
B[1]:=B[1]=-14717113539487181/715391356779;
B[m_]:=B[m]=(1+Floor[B[m-1]]*B[m-1])/(Floor[B[m-1]]-B[m-1]);
coeff=(10+I)^8*(100+I)^-1*(1000+I)^-2*
Product[(Floor[B[m]]+I)^-1,{m,1,18}];
Re[coeff]==Im[coeff]
returns True for validation of the Equation (22).
As we have reported in [24] , the arctangent function can be expanded as a series
Using this series expansion we can obtain the following relation
where the quotient on the right side can be eliminated by using Equation (13) in iterative procedure. Therefore, there is a possibility to rearrange the Equation (12) with starting term 80 arctan (1/100). This may be more advantageous in computation due to faster convergence.
4. Lehmer’s Measure
According to definition (3), the Lehmer measure for the Equation (22) is
However, the measure may be reduced under some specific criteria. In particular, Lehmer justifiably noticed that the actangent terms of kind
are much easier to calculate (see [1] , page 662). Therefore, he suggested to assign the measure 1/2 for the arctangent term arctan (1/10). Moreover, Lehmer also pointed out that if a Machin-like formula for π besides arctan (1/10) includes the arctangents of other powers of 1/10, then the measure 0 should be assigned to all of them since the Maclaurin series expansion (2) of arctan (1/10) already contains all required digits in mantissa of each term that can be used further for computation of arctan (1/10m). More explicitly, once in accordance with Equation (2) we compute
then the computation
becomes straightforward since it can be implemented algorithmically just by decreasing exponent in each term while keeping mantissa absolutely unchanged. Consequently, as Lehmer suggested [1] if arctan (1/10) is present in a given relation, then for each arctangent term arctan (1/10m) the measure 0 can be assigned. Thus, the Lehmer measure for the Equation (22) can be reduced as
The corresponding Mathematica code is:
Clear[B]
B[1]:=B[1]=-14717113539487181/715391356779;
B[m_]:=B[m]=(1+Floor[B[m-1]]*B[m-1])/
(Floor[B[m-1]]-B[m-1]);
Print["The Lehmer measure of identity (22) is: ",
1/2+0+0+Sum[1/Log10[Abs[B[m]]],
{m,1,18}]//N]
The generated output is:
The Lehmer measure of identity (22) is: 0.956916
As we can see from this example, the Lehmer measure below one can be achieved in a Machin-like formula for π without any quotient and at a smaller values of the integer k. Despite that the initial formula (12) for π that we used as a starting point in iterative procedure, corresponds to the small integer
, this method enables us to generate the multi-term Machin-like formula (22) for π with Lehmer measure less than unity,
.
Consider for comparison the following two Machin-like formulas for π that also include three arctangent terms with arguments 1/10, 1/100 and 1/1000 [25]
(23)
and
(24)
The corresponding Lehmer measures are
and
respectively. As we can see, the Machin-like formula (22) for π is computationally more efficient since its Lehmer’s measure is significantly smaller.
The computation of the first three arctangent terms in Equation (22) can be implemented by using the Maclaurin series expansion (2) since in decimal system no actual multiplications in determination of powers of 1/10 are needed (as mentioned, this can be done only by decreasing exponent and keeping mantissa unchanged in each term). However, starting from the forth arctangent term arctan (1/20573) application of the Maclaurin series expansion (2) may not be optimal since faster convergence rate can be achieved by using either Euler’s formula [26] [27]
(25)
or iteration-based formula [24]
(26)
where
Chien-Lih showed an elegant derivation of the Euler’s formula (25) by an elementary method [27]. In particular, this series expansion can be derived by taking integral
in terms of geometric series
Iteration-based Equation (26) represents a trivial rearrangement of the series expansion
that we derived in our work [28].
It should be noted that apart from decimal system, other number systems can also be used in the Machin-like formulas for π. For example, a more rapid computation of the Maclaurin series expansion (2) can also be achieved for the arctangent terms like arctan (1/8m) and arctan (1/16m) in octal and hexadecimal systems, respectively.
5. Klingenstierna’s Identity
The method described above can also be used to derive some known Machin-like formulas for π. This derivation is much easier than the conventional derivations. For example, solving
and representing the last arctangent term from Equation (17) as
we immediately get the well-known identity
According to Castellanos, this identity is attributed to Swedish mathematician Samuel Klingenstierna [26]. Although the corresponding measure
is relatively small, this Machin-like formula may not be optimal for computing π due to quotient in its last arctangent term.
6. Alternative Representation
It is interesting to note that a slight modification of the identity (13) as given by
(27)
can also be used to generate the Machin-like formulas for π. Return to Equation (12) again and assume that
For, say,
substituting this value z into identity (27) leads to
(28)
Similarly, substituting now
into identity (28) results in
(29)
The following Mathematica code:
coeff=(10+I)^8*(83+68/100+I)^-1*
(307888297107/412123+I)^-1;
eq28=Re[coeff]==Im[coeff];
coeff=(10+I)^8*(83+68/100+I)^-1*(747078+66/100+I)^-1*
(11500838821639577981/74409+I)^-1;
eq29=Re[coeff]==Im[coeff];
Print[{eq28,eq29}]
validates Equations (28) and (29) by returning the list {True,True}.
Thus, using the iteration above, we can derive the following Machin-like formula for π
(30)
consisting of 10-terms with finite number of decimal digits in each arctangent term.
The 10-term Machin-like formula (30) for π can be represented in a compact form as follows
where
and
Iteration is completed at 9th step since (see [19] for a detailed description of iteration procedure)
is an integer.
The following Mathematica program:
Clear[B]
B[1]:=B[1]=-147153121/1758719;
B[m_]:=B[m]=(1+(Floor[10^2*B[m-1]]*10^-2)*
B[m-1])/((Floor[10^2*B[m-1]]*
10^-2)-B[m - 1]);
coeff=(10+I)^8*Product[(Abs[Floor[10^2*B[m]]*
10^-2]+I)^-1,{m,1,9}];
Re[coeff]==Im[coeff]
validates Equation (30) by returning True.
7. Conclusion
A method that can be used to generate a multi-term Machin-like formula for π with a reduced Lehmer measure is presented. We show that the Lehmer measure below 1 can be achieved even at small value of the integer
. Specifically, as an example we derive the Machin-like formula (22) for π with the Lehmer measure
. This value is significantly smaller than the smallest Lehmer measure 1.34085 known so far among the Machin-like formulas for π consisting of only integer reciprocals.
Acknowledgements
This work is supported by National Research Council Canada, Thoth Technology Inc., York University and Epic College of Technology.