Home page     Evaluation of PI
Database of reductions        Database of identities

MACHINATION SOFTWARE PACKAGE

N.B.: THE NOTATION "[x]" IS USED TO REPRESENT "arccot(x)" (= arctan(1/x)) THROUGHOUT THIS SITE.

To assist us in finding new identities, we ourselves have used a PC software package (entirely designed and written by Michael Wetherfield, mostly in C with some ASM routines, ongoing since 1991) named "Machination" in honour of John Machin (1680-1751). The component programs run under MS-DOS, and include Batch files of MS-DOS commands. Windows 98 SE has proved an excellent multi-tasking environment, Windows XP (because of its lack of friendliness towards DOS - e.g. ">" and ">>" symbols in Batch files are not "echoed" correctly) less so!

For computational purposes, cotangent values are (usually) represented internally as 64-bit fixed-point integers (these, and the numerators of "half-integer" values - one bit of the 64 is used to "flag" the latter - may therefore have up to 19 decimal digits), and the coefficients used in solving the simultaneous linear equations as 96-bit signed fixed-point integers (this appears adequate for dealing with up to 29 "eliminands").

The software by now includes three programs for performing "Todd reductions". The first of these saw the light of day (as a C/MASM version) in 1992, after a gestation period of some 25 years (it was originally written in ICL's "S3" language). It operates on integer or fractional cotangent values - in the latter case, with virtually any denominator less than the numerator - the maximum integer value being the comparatively low 2147483647. However it imposes no ceiling on irreducibles, i.e. any reducible integer not exceeding that value will be reduced, however large the primes associated with its irreducible terms; and if the value is itself irreducible, the associated prime (and its unique quadratic decomposition) will be output. In order to factorise (N² + 1), the program looks for alternative quadratic decompositions. There are no plans to adapt this version to allow larger arguments; however, another utility exists which, given a number (congruent to 1, modulo 4) whose value may be up to 27 decimal digits long, will determine whether or not this number is prime, and if it is prime, will output its quadratic decomposition and the cotangent value of the associated irreducible - this is a useful tool when dealing with the results of "tweaking".

The two later Reduction programs, which operate on integer or half-integer values, both impose a limit on the permitted irreducibles (i.e. on the size of the "largest associated prime"); the general-purpose version uses fixed-point arithmetic, and allows 63-bit input values, the other version (used only by the "sieve" technique mentioned in the "DATABASE OF REDUCTIONS" section below) uses the 8-byte floating-point format.

Top of page

INVERSE FRACTIONAL COTANGENTS

Originally the terms appearing in our lists were restricted to inverse integer cotangents, the presence of half-integer terms being justified because (apart from "improving" the identities they appear in) they could be conveniently represented as pairs of integers. Nowadays we accept them for what they are. A good case could probably be made out for including fractional cotangent values with denominators greater than 2, because, as with half-integers, computer programs to evaluate their inverses should be no more difficult to write than those for integer cotangent values, and it is possible that such terms could be used to enhance identities. However we have no plans to include such values.

 
DATABASE OF REDUCTIONS

For every Todd reduction of an inverse integer cotangent [N], or half-integer cotangent [N/2], there is a "largest prime" defined, viz. the largest prime factor of (N² + 1), or, for half-integers, of (N² + 4). Every reduction forming part of this database, on which most of the software operates, is held in a unique text file determined by the irreducible associated with its largest prime. Reductions for which the largest prime is less than 100 share a single file, but for each prime value greater than 100 there is a separate file. The sizes of these files, which in practise cater for primes up to at least 1597, vary greatly; the larger the prime, the bigger the file. For primes up to 1201 (associated irreducible [49]), the files have now been completed, using a "sieve" technique, for all reducible integer cotangent values up to [9999 99999 99999], and for half-integer values up to [19999 99999 99999/2].

The above-mentioned "sieve" technique for extending files of reductions is quite efficient because it ignores all values [N] and [N/2] except those for which the prime associated with the file being extended divides (N² + 1) or (N² + 4), and the reduction process* was originally also simplified, because not only is the largest prime value pre-defined, but also 'N' could, in this context, be represented in 64-bit floating-point format; however, because this also necessarily applies to the intermediate values occurring in the reduction process, in some cases the target limits of [9999 99999 99999] for integer values, and [19999 99999 99999/2] for half-integer values, could not be achieved. To complete the files up to the desired limits, less efficient alternative routines based on the same "sieve" technique, but operating on cotangent values in fixed-point format, have now been used (however, it would have taken much too much time to use these routines to progress very far beyond these limits).

Top of page

"OUTSIZE" REDUCIBLE INVERSE COTANGENTS

A very useful extrapolation process has been devised to find reductions of "outsize" inverse integer cotangent values lying beyond the 10^14 limit (as mentioned above, values with up to 19 decimal digits are admitted). This process depends on finding integer "pair" equivalents** for large inverse integer, or half-integer, cotangents, and then in turn for likely members of the pairs thus found, and so on; quite often these pair members turn out to be new eligible "outsize" values (to which the process is also applied), where "eligibility" implies a "largest prime" not greater than 1201. Inevitably, the new values found using "extrapolation" can represent only a subset of the totality of reducibles.

Unfortunately, this process could not be used to find "outsize" half-integer reducibles, but recently (August 2011) a program designed explicitly to rectify this deficiency has been successfully tested and run. This new program makes use of a technique which is, in effect, the opposite of the extrapolation process: instead of using existing reducibles to generate pairs of integer reducibles, some of which are, hopefully, new, this technique relies on the fact that most half-integer reducibles can be represented (often in more than one way) as the difference of two integer reducibles; accordingly, the program examines the differences of all possible pairs of known integer reducibles which (a) have at least 9 digits and (b) are present in the database of reductions in any of the files associated with primes from 157 (irreducible [28]) up to 1201 (irreducible [49]), to determine which of the resultant reducible fractional cotangents have denominator 2. This has resulted in the generation of more than 1500 new "outsize" half-integer reducibles with numerators greater than 19999 99999 99999 (and these half-integers have themselves been input to the "extrapolation" process and thus led in turn to the generation of a significant number of new "outsize" integer reducibles).

This technique has also been applied, with greater success than initially expected, to testing "differences" within individual files of integer reducibles associated with primes greater than 1201 (in this case the "differencing", as well as generating a half-integer result, has to ensure that all the irreducibles in the "pair" with associated primes greater than 1201 are eliminated as well) - with the result that virtually all available computing time is now being used in extending these files (using the "sieve" technique) to include all 14-digit cotangent values.

Top of page

A useful alternative method of obtaining eligible outsize values was at one time provided by another utility, specifically designed to generate values whose reductions "match" a given set of irreducibles, i.e. involving only members of this set. The irreducibles comprising this set are input as parameters to the utility, whose modus operandi depends on the fact that if a reduction* (of [N], say) includes a term ±C[I], where I is an irreducible associated with a prime P and the integer C is the absolute value of the coefficient of [I] in the reduction, it is virtually certain that P (raised to the power C) is a factor of (N²+1); also, the product of the square roots of all the factors of (N²+1) will aproximate very closely to the integer N. The utility first assigns limits to the value of C for each irreducible in the set - in increasing "associated prime" sequence, these limits are 1 for the irreducible [1] (P=2) (inevitably, since 2 can only occur once as a factor of (N²+1)), 12, 8, 7 and 6 for [2] (P=5), [5] (P=13), [4] (P=17) and [12] (P=29) respectively, 5 for [6] (P=37) to [27] (P=73) inclusive, 4 for [34] (P=89) to [14] (P=197) inclusive, 3 for [107] (P=229) to [585] (P=1249) inclusive, and 2 for any remaining eligible irreducibles. The utility then computes all possible products of the square roots of the primes associated with the irreducibles in the set, each root being raised to a power which may range from 0 up to its assigned limit - thus, if [14] is a member of the set, the factor it contributes to the product may be unity, or the square root of 197 raised to the power 1, 2, 3 or 4. For an even power, the factor is obviously an integer - the product is only valid if at least one power is odd. Floating-point arithmetic is used, the product and all its factors being held in the Intel 10-byte "temporary real" format which allows 64-bit precision - all non-integral square roots are rounded up, and the utility looks for products which have a minuscule fractional component; if this is the case the integer component is checked for reducibility and whether its reduction matches the given set of irreducibles. This utility, which may also be used to find half-integer values, has in its time delivered valuable results in some cases when there was a suspicion that an identity with a particular "eliminated set" of irreducibles could be improved (one symptom being an unusually large coefficient for [1] on the LHS). It is also satisfyingly exhaustive, in that it very, very rarely "misses out" any of the already-known outsize values which match the given irreducibles. Its main drawback is slowness, but it can be stopped at suitable points and restarted. The restriction implied by the limits imposed on the coefficient C, the power to which a particular prime may be raised, somewhat devalued the process; for example, since 389^5 is a factor of (27967735106090² + 1) - the largest prime factor is 761 - [2796 77351 06090] would elude discovery by this technique as it stands (however, this is a truly exceptional case).

*The reduction process is described elsewhere on this site (refer to Home Page).

**The process of finding "pair" (and "triplet") equivalents is described elsewhere on this site - see "More Detail" in the pages on "Tweaking" (refer to Home Page).

Top of page
DATABASE OF IDENTITIES

The lists of identities displayed on this website represent the tip of a large iceberg. For identities whose "D" value (D = number of decimal digits in the identity's least cotangent value) is 4 or more, usually only the "top 20" in each category are shown, though we actually maintain a very large database of those not in the "top 20". Eligible entries for this database have the property that the identity must be completely defined by its "eliminated set" of irreducibles - this excludes identities obtained by "tweaking"***, but usually includes the "untweaked" originals. Identities whose measures are significantly larger than those in the "top 20" are excluded. Also excluded are those (untweaked) identities in which one or more irreducibles remain uneliminated and appear in the identity - but such identities naturally have "D" values of 3 or less, anyway.

The database entry for each identity includes only its measure and the list of irreducibles, which suffices to reconstruct the identity. Whenever a new entry is added to the database of reductions, it can be checked against the identity database to see whether any identity which includes the same irreducibles is "improved" (i.e. has its measure reduced) by its presence.

The serendipitous discovery in 2004 of the 3-digit identity with measure 1.26579 demonstrates some of the facilities afforded by the software. One of the editors (MRW) used one of the standard Machination utilities with a simple MS-DOS batch program to search for identities based on seven irreducibles: [2], [4], and five "wild cards" (specifically excluding [5]). "Reducible" cotangent values having less than 4 digits were automatically rejected. One of the resultant identities was shown as having measure 1.79286, with the following "eliminated set" of irreducibles: [2], [4], [15], [28], [33], [107], [249]. Out of curiosity MRW decided to expand this entry to reconstruct the full identity, but then, having inadvertently input the irreducible [5] instead of [4], to his great surprise the computer output the following identity (shown here preceded by the five eligible entries from the database of reductions):

  [1710]= [1] - 2[2] + 2[15] + [107]
  [2513489/2]= -6[1] + 10[2] + [15] + [107]
  [105218]= [1] - 2[2] + [15] + [28] + [33] + [107]
  [279258]= [1] - 3[2] + 3[5] + [107] + [249]
  [7167807]= 3[1] - 5[2] - [28] - [33] + 3[107]
[1] = 83[107] + 17[1710] - 12(2[2513489]-[7939642926390344818]) - 22[105218] - 22[7167807]
Measure (pre-Aug06 version, i.e. with the "two integer" representation of [2513489/2]): 1.35622

It is worth observing that [5] and [249] both appeared only once, in the reduction of [279258], and so were eliminated by the omission of that reduction; and that from the remaining four reductions it was still possible to eliminate [2], [15], [28], and [33] (but not [107]) because [28] and [33] were in this context "Siamese twins" and could be eliminated together. In the light of experience, a remarkable feature of this identity is that, apart from 5, none of the prime numbers associated with the irreducibles eliminated is less than 109.

The presence of two terms with the same coefficient (-22) enabled this identity to be "tweaked"***, replacing [105218]+[7167807] by [103697]+[18280007883/2] and thereby generating the improved version with measure 1.26579 (pre-Aug06: 1.34085).

***See the pages on "Tweaking" (refer to Home Page).

Top of page