Enumeration to 1.6e15 of the prime quadruplets

Thomas R. Nicely

http://www.trnicely.net
Current e-mail address


Freeware copyright (c) 2010 Thomas R. Nicely. Released into the public domain by the author, who disclaims any legal liability arising from its use.

Last revised 1000 GMT 18 January 2010.

Date of first release 23 August 1999.

The content of this document (other than the addendum, which was not part of the submission for publication) is essentially that of the original release, except that information rendered obsolete by subsequent events has been removed or modified, in both the main document and the addendum (this liberty is taken in view of the fact that the paper was never accepted for publication). There may also be differences in formatting, and in minor details and corrections, such as updated URLs.

Abstract

Enumeration of the prime quadruplets (q, q+2, q+6, q+8), and the sum of their reciprocals, is extended to 1.6e15. An estimate is obtained for the limit of the sum of the reciprocals, an analog to Brun's constant, B_4 = 0.87058 83800 +/- 0.00000 00005. Error analysis is presented to support the opinion that the stated error bound represents a 99% confidence level.

Mathematics Subject Classification 2000 (MSC2000)

Primary: 11A41.
Secondary: 11-04, 11Y70, 11Y60.

Key Words and Phrases

Prime numbers, prime quadruplets, prime constellations, Brun's constants, prime k-tuples conjecture.


1. Introduction

Certain groupings (k-tuples, or constellations) of two or more prime numbers, such as the twin-prime pairs K_2 = {(3, 5), (5, 7), (11, 13), (17, 19), ...}, are believed to constitute infinite sets. Other such groupings may occur only a finite number of times, and perhaps not at all; e.g., the prime triplets (q, q+2, q+4) produce only the one instance (3, 5, 7), while there are no prime triplets at all of the form (q, q+1, q+2). Constellations which, due to divisibility considerations and the resulting residue classes occupied, can have only a finite number of instances (possibly none), are termed inadmissible; the remaining constellations are termed admissible. The question of infinitude remains undecided for all the admissible constellations; in the case of the twins, the proposition of infinitude is referred to as the "twin-primes conjecture." Hardy and Littlewood [4] conjectured a much stronger and more quantitative description of the distribution of the admissible constellations, the "prime k-tuples conjecture," which imples not only the infinitude of every admissible constellation, but yields also quite accurate asymptotic formulas for the number of members of a particular admissible constellation which lie below a specified upper bound x.

2. The Prime Quadruplets

Most of the study of the prime constellations has been focused on the twin primes; see [7] and [9] for some recent results. This paper considers instead the constellation of prime quadruplets of the form (q, q+2, q+6, q+8), the set
(2.1)  K_4 = {(5, 7, 11, 13), (11, 13, 17, 19), (101, 103, 107, 109), ...} ,
in which the first element of each member (except the anomalous initial one) is of the form 30n + 11. As with other admissible constellations, it is not known if K_4 is infinite. It is known that there exist extremely large numbers and instances of such prime quadruplets; more than a thousand million of them have been counted beyond 1e15 in this study, and Forbes [2] reports an instance in which the initial prime is a number of 1032 decimal digits,
(2.2)  q = 24947432928741915235*(2^3363 - 2^1121) - 6*(2^1121) - 7 .
Furthermore, the Hardy-Littlewood prime k-tuples conjecture implies that
(2.3)  pi_4(x) ~ L_4(x) = (27/2)*c_4*int(1/(ln(t))^4, t, 2, x) ,
where pi_4(x) represents the count of prime quadruplets (q, q+2, q+6, q+8) such that q <= x, and c_4 is the constant
(2.4)  c_4 = prod((p^3)*(p - 4)/(p - 1)^4, p, 5, +infinity) ,
with the infinite product taken over all the primes save 2 and 3. We shall refer to (2.3) as the Hardy-Littlewood approximation for the prime quadruplets, or simply the Hardy-Littlewood approximation; it clearly implies the infinitude of the quadruplets, and a great deal more. The validity of this conjecture will be central to our methods for estimating B_4 and its error bound. See Riesel [11, pp. 60-83] for detailed discussions and derivations of (2.3), (2.4), and similar consequences of the prime k-tuples conjecture. The constant c_4 has been computed to 45 significant digits by Harley [5],
(2.5)  c_4 = 0.30749 48787 58327 09312 33544 86071 07685 30221 78519...
For the twin primes, Brun [1] proved that whether or not the set K_2 is infinite, the sum of the reciprocals
(2.6)  B_2 = (1/3 + 1/5) + (1/5 + 1/7) + (1/11 + 1/13) + (1/17 + 1/19) + ... ,
is convergent, in contrast to the known divergence of the sum of the reciprocals of all the primes. The limit of this sum is now referred to as Brun's constant,and has been approximated by Nicely as
(2.7)  B_2 = 1.90216 05832 +/- 0.00000 00008  ,
where the error bound is believed to represent at least one standard deviation.

In the same fashion, we define Brun's constant B_4 for the prime quadruplets as the limit of the sum of the reciprocals,

(2.8)  B_4 = (1/5 + 1/7 + 1/11 + 1/13) + (1/11 + 1/13 + 1/17 + 1/19)
                  + (1/101 + 1/103 + 1/107 + 1/109) + ...
As with B_2, we do not if the series is finite or infinite; but as a consequence of Brun's proof of the convergence of the sum of the reciprocals of the twins, we do know that the series for B_4 is convergent; for if the series is infinite, its terms are a proper subset of the series in (2.6). Since (2.6) is a positive series, its convergence is immune to deletion, rearrangement, or regrouping of terms; thus the series (2.8) defining B_4 must also be convergent. In essence, the quadruplets are constructed from a proper subset of the twins.

Although (2.8) is convergent, the monotonically increasing partial sums approach the limit quite slowly. However, assuming the validity of the Hardy-Littlewood approximation (2.3), a more rapidly converging first order extrapolation may be derived as follows. Define S_4(x) as the partial sum of the reciprocals of the quadruplets,

(2.9)  S_4(x) = sum(1/q + 1/(q+2) + 1/(q+6) + 1/(q+8), q, q <= x) .
Then the remainder term in the series defining B_4 may be approximated by
(2.10)  B_4 - S_4(x) = sum(1/q + 1/(q+2) + 1/(q+6) + 1/(q+8), q, q > x)
                     ~ int((4/t)*(27c_4/2)*1/(ln(t))^4, t, x, +infinity)
                     ~ 54c_4*int(1/(t*(ln(t))^4)), t, x, +infinity)
                     ~ 54c_4*int(1/u^4, u, ln(x), +infinity)
                     ~ 18c_4/(ln(x))^4 ,
where we have employed the density (27/2)c_4*1/(ln(t))^4 of quadruplets implied by the Hardy-Littlewood approximation, approximated the sum of the reciprocals of a particular quadruplet by 4/t, and used the substitution u = ln(t). This produces a "first order" extrapolation of S_4(x) to B_4, which we denote by F_4(x),
(2.11)  B_4 ~ F_4(x) = S_4(x) + 18c_4/(ln(x))^3
No effective second order extrapolation is known; however, we will present evidence that the error term in (2.11) is O(1/(sqrt(x)*(ln(x))^2), so that
(2.12)  B_4 = F_4(x) + O(1/(sqrt(x)*(ln(x))^2))
            = S_4(x) + 18c_4/(ln(x))^3 + O(1/(sqrt(x)*(ln(x))^2)) ,
implying that F_4(x) converges to B_4 at a rate O(sqrt(x)/ln(x)) faster than the partial sums S_4(x).

3. Computational Results

The present study results from the continuation of a project initiated in 1993, an exercise in the use of distributed computing to leverage limited resources (personal computers of moderate cost and power) in order to attack problems in computational number theory which normally would be reserved to supercomputers. Detailed descriptions of the general program, the computational methods employed, and the incidental discovery of the Pentium FDIV flaw may be found in [7], [8], [9], and [10].

Table 1 contains a brief summary of the computational results, including the counts pi_4(x) of the prime quadruplets (q, q+2, q+6, q+8); the values of the discrepancy between pi_4(x) and the Hardy-Littlewood approximation,

(3.1)  delta_4(x) = L_4(x) - pi_4(x) ;
the partial sums S_4(x) of the reciprocals of the quadruplets; and the first order extrapolations F_4(x) of S_4(x) to the limit, according to (2.11), members of a sequence believed to be converging to Brun's B_4 constant.


                               Table 1.
  Counts of prime quadruplets and estimates of Brun's B_4 constant.
======================================================================
     x      pi_4(x) delta_4(x)        S_4(x)             F_4(x)
======================================================================
   1e01           1      10.29  0.510689310689311  0.964070321217938
   1e02           2      11.60  0.789976586880612  0.846649213196690
   1e03           5      11.49  0.853473194253130  0.870265083531968
   1e04          12      12.17  0.863733192400183  0.870817270689693
   1e05          38      14.88  0.867011003684134  0.870638051768363
   1e06         166      17.68  0.868379532753497  0.870478518913352
   1e07         899     -36.05  0.869267876960829  0.870589687487152
   1e08        4768     -33.36  0.869705293632323  0.870590803418512
   1e09       28388       8.84  0.869966856425087  0.870588778250229
   1e10      180529     545.93  0.870134891176928  0.870588272187457
   1e11     1209318     638.22  0.870247695545365  0.870588327409023
   1e12     8398278   -3699.97  0.870326020813441  0.870588394083423
   1e13    60070590    4848.36  0.870382016088034  0.870588379770569
   1e14   441296836   -6103.68  0.870423153466140  0.870588379781931
   2e14   807947960    2717.36  0.870433368925933  0.870588379517423
   3e14  1151928827  -12660.14  0.870438957019776  0.870588379757893
   4e14  1482125418  -15032.60  0.870442759816539  0.870588379787802
   5e14  1802539207  -23557.26  0.870445621161320  0.870588379871401
   6e14  2115416076  -35177.17  0.870447903679533  0.870588379961704
   7e14  2422194981  -49882.89  0.870449795732922  0.870588380059497
   8e14  2723839871  -35301.69  0.870451407176393  0.870588379983029
   9e14  3021126140  -38141.52  0.870452807976233  0.870588379996686
   1e15  3314576487  -26197.22  0.870454044834374  0.870588379948604
 1.1e15  3604646822  -19485.07  0.870455150797010  0.870588379922608
 1.2e15  3891706125  -36034.00  0.870456149967533  0.870588379981021
 1.3e15  4175985018  -18182.67  0.870457060200978  0.870588379923299
 1.4e15  4457782901  -24552.75  0.870457895584737  0.870588379943262
 1.5e15  4737286827  -38254.45  0.870458666969910  0.870588379980055
 1.6e15  5014641832  -29496.94  0.870459383002448  0.870588379958289
======================================================================

The count pi_4(1e8) in Table 1 agrees with the value attributed by Riesel [11, p. 62] to Gruenberger and Armerding [3]. Two values omitted from Table 1, pi_4(2e9) = 49262 and pi_4(2e10) = 319107, agree with those computed by Hein [6]. Additional checks on the integrity of the results included comparisons of the associated values of pi(x) with published values, and duplications of each calculated interval on two different computer systems. The computed values of pi(x) are not shown here, but are available at http://www.trnicely.net/pi/tabpi.html. Also, more extensive versions of Table 1 are available at http://www.trnicely.net/quads/t4_0000.htmhttp://www.trnicely.net/quads/t4_0001.htm, and at this site.

No previous investigator is known to have considered the sums of the reciprocals, or Brun's B_4 constant.

In support of the accuracy and probable validity of the Hardy-Littlewood conjecture (2.3) for the quadruplets, note that delta_4(x) has about half as many digits as L_4(x). This also supports the deduction

(3.2)  delta_4(x) = O(sqrt(L_4(x)) = O(sqrt(x)/(ln(x))^2) .
Furthermore, this would correspond to an error term in the first order extrapolation (2.11) of order
(3.3)  B_4 - F_4(x) = O((4/x)*sqrt(x)/(ln(x))^2)
                   = O(1/(sqrt(x)*(ln(x))^2)) ,
supporting the error term proposed in (2.12). The consequent consistency of the extrapolated estimates F_4(x) for Brun's B_4 constant provides additional evidence in favor of the Hardy-Littlewood approximation.

4. Brun's B_4 Constant and the Error Analysis

The first order extrapolation F_4(1.6e15) is believed to yield an estimate of Brun's B_4 constant accurate to ten significant decimal digits,
(4.1)  B_4 = 0.87058 83800 +/- 0.00000 00005 .
The error estimate is believed to represent a 99 % confidence level, although this is a subjective opinion of the author for which definitive proof remains lacking. More precisely, the author believes that for at least 99 % of the integers in any sufficiently large set of distinct integers x > 1, Brun's B_4 constant would lie between F_4(x) - E_4(x) and F_4(x) + E_4(x). Here E_4(x) is the error bound function stated in (4.6) below, from which the error bound in (4.1) will be obtained. The error estimate is arrived at as follows.

Rather than attempting to bound the error F_4(x) - B_4 directly, we consider the "scaled deviations"

(4.2)  P_4(x) = sqrt(x)*((ln(x))^2)*[F_4(x) - B_4] ,
where the scaling factor sqrt(x)*(ln(x))^2 arises from the conjectured error term in (2.12). No rigorous derivation is known for this error term. One justification for it was given in the derivation of (3.3), based on the observed magnitude of delta_4(x) in the computed data. A second justification arises from further analysis of the data, which reveals that the resulting mean absolute value of P_4(x) (using our best estimate F_4(1.6e15) in place of B_4) remains of the same order of magnitude O(1) over most intervals of 10^12 from 0 through 1.6e15, as would be expected with a valid scaling factor (deviations at all values of x are thus given similar weight).

We now hypothesize that the deviations F_4(x) - B_4 (and consequently P_4(x) as well) change sign infinitely often; more precisely, given any x_0, however large, there will exist integers x_1 > x_0 and x_2 > x_0 such that F_4(x_1) < B_4 and F_4(x_2) > B_4. We will refer to this as hypothesis [H4]. Note that although [H4] is neither necessary nor sufficient for the Hardy-Littlewood approximation (2.3), it will almost certainly fail (along with (4.1) in its entirety) if Hardy-Littlewood is false. In support of [H4], we note that if our best estimate F_4(1.6e15) is used for B_4, then F_4(x) - B_4 is observed to undergo 504 sign changes over the 160081 data points recorded in the present study, with 315 sign changes occurring beyond 10^15.

Given [H4], we then look for the maximum computable value of the function

(4.3)  N_4(x_1, x_2) = sqrt(x_1)*((ln(x_1))^2)*|F_4(x_1) - F_4(x_2)| ,
where x_1 and x_2 are integers such that x_2 > x_1 > 1. N_4 may be considered as a "normalized" measure of the amplitude of the oscillations in F_4(x), or alternately as a measure of the scaled deviation of a "predictor" value F_4(x_1) from a "terminal approximation" F_4(x_2). In contrast to P_4, N_4 has the virtue that it is independent of the uncertain value of B_4. If N_4 has a global maximum, or even an upper bound, then given [H4] this must also represent an upper bound on the absolute value of P_4, thus producing an unconditional error bound; for any specific value |P_4(x_3)| will be exceeded by N_4(x_3, x_4), where x_4 is chosen so that x_4 > x_3 while F_4(x_3) - B_4 and F_4(x_4) - B_4 are of opposite sign ([H4] implies that there is an infinite sequence of such integers x_4 for any given integer x_3). In practice, we are unable to prove that N_4 has a global maximum, although (2.12) would imply that P_4 is bounded. Indeed, it is computationally impractical even to find the absolute maximum of N_4 over all integers in the range under investigation, 1 < x_1 < x_2 <= 1.6e15; this would involve the comparison of more than 1e30 data pairs (F_4(x_1), F_4(x_2)), a calculation of doubtful feasibility. What has been determined is that the absolute maximum of N_4 over all of the (more than 10^10 such) data pairs recorded in this study is
(4.4)  N_4(1000000, 20000000) = 21.704105  .
However, additional computations reveal an even larger value of N_4 in the vicinity of this point,
(4.5)  N_4(1002340, 16977221) = 22.6687145 ,
where the values in both (4.4) and (4.5) have been rounded up. Although the value 22.6687145 is still not established as the sought after upper bound on N_4 (and thus on |P_4|), the numerical evidence (zero exceptions among more than 1e10 data pairs extending over fifteen orders of magnitude) indicates that if any larger values of N_4 (and thus |P_4|) exist, they must be relatively rare. Our intuitive conclusion is that for the great majority (99 percent or more?) of integers x > 1, it will be true that |P_4(x)| < 22.6687145, producing the error bound formula E_4(x),
(4.6)  |F_4(x) - B_4| < E_4(x) = 22.6687145/(sqrt(x)*(ln(x))^2) .
In arriving at our error estimate in (4.1), we are assuming that (4.6) does in fact hold specifically for x = 1.6e15, so that
(4.7)  |F_4(1.6e15) - B_4| < E_4(1.6e15) = 22.6687145/(sqrt(1.6e15)*(ln(1.6e15))^2) ,
giving
(4.8)  |F_4(1.6e15) - B_4| < 0.00000 00004 624 ,
which, with rounding up for good measure, produces the error estimate given in (4.1).

The validity of the Hardy-Littlewood conjecture (2.3) is critical to our estimate (4.1) of Brun's B_4 constant and the associated error bound. On the other hand, the particular scaling factor sqrt(x)*(ln(x))^2, taken from the conjectured error term in (2.12), is not indispensable to this line of error analysis. Alternative scaling factors could be employed, presumably corresponding to different error terms, and the author in fact investigated several alternatives. No other yielded superior results; either the resulting error bound was inferior, or a "near-maximum" value of the corresponding function N_4 (meaning one sufficiently large to provide an error bound of equal or better confidence level) could not be located without greatly escalating the computational effort. One notable virtue of this scaling factor was that the resulting maximum computed value of N_4 occurred at relatively small values of x_1 and x_2, permitting a detailed search for the extreme value, and yielding an increased confidence that larger values would prove difficult to unearth, or perhaps even be nonexistent. Nonethless, some other alternative scaling factor might yet produce a superior error bound.

On the other hand, more than ten thousand million pairs of first order extrapolations have agreed with each other within this error bound, without exception. Of course, it carries no unconditional guarantee; overwhelming numerical evidence is occasionally a subtle trap, as the conjecture Li(x) > pi(x) so memorably illustrated. However, it would appear that a more rigorous error bound must await a deeper understanding of the subtleties in the distribution of the prime quadruplets in particular, and the prime constellations in general.


References

  1. Viggo Brun, "La série 1/5 + 1/7 + 1/11 + 1/13 + 1/17 + 1/19 + 1/29 + 1/31 + 1/41 + 1/43 + 1/59 + 1/61 + ..., où les dénominateurs sont 'nombres premieres jumeaux' est convergente ou finie," (French) Bulletin des sciences mathématiques 43 (1919), 100-104, 124-128.
  2. Tony Forbes, unpublished work, accessed 5 August 1999; Web document no longer accessible.
  3. F. J. Gruenberger and G. Armerding, "Statistics on the first six million primes," UMT 73, Math. Comp. 19 (1965), 503-505.
  4. G. H. Hardy and J. E. Littlewood, "Some problems of 'Partitio Numerorum' III: On the expression of a number as a sum of primes," Acta Math. 44 (1922), 1-70. See also "Collected papers of G. H. Hardy," Clarendon Press, Oxford, 1966, Vol. I, 561-630.
  5. Robert Joseph Harley, unpublished work, accessed 16 September 1996; Web document no longer accessible.
  6. Robert Hein <rhein(AT)erols(DOT)com>, unpublished work (3 March 1995), received by telefax from U. S. Army CECOM RDEC, Intelligence and Electronic Warfare Directorate, Data Fusion Branch, ECM Lab, Vint Hill Farms Station, Warrenton VA 22186-5100 USA.
  7. Thomas R. Nicely, "Enumeration to 1e14 of the twin primes and Brun's constant," Virginia Journal of Science 46:3 (Fall, 1995), 195-204. MR1401560 (97e:11014). Reprint available electronically at http://www.trnicely.net/twins/twins.html.
  8. Thomas R. Nicely, "New maximal prime gaps and first occurrences," Math. Comp. 68:227 (July, 1999), 1311-1315. MR1627813 (99i:11004). Reprint available electronically at http://www.trnicely.net/gaps/gaps.html.
  9. Thomas R. Nicely, "A new error analysis for Brun's constant," Virginia Journal of Science 52:1 (Spring, 2001), 45-55. MR1853722 (2003d:11184). Reprint available electronically at http://www.trnicely.net/twins/twins4.html.
  10. Thomas R. Nicely and Bertil Nyman, "First occurrence of a prime gap of 1000 or greater," unpublished (21 May 1999), available electronically at http://www.trnicely.net/gaps/gaps2.html.
  11. Hans Riesel, "Prime numbers and computer methods for factorization," 2nd ed., Birkhäuser, Boston, 1994. MR 95h:11142.

Addendum

NOTE: This addendum was not part of the original submission for publication.