Introduction to twin primes and Brun's constant computation Introduction to twin primes and Brun's constant computation (Click herefor a Postscript version of this page and herefor a pdf version) 1 IntroductionIt's a very old fact (Euclid 325-265 B.C., in Book IX of the Elements) that the set of primes is infinite and a much more recent and famous result(by Jacques Hadamard (1865-1963) and Charles-Jean de la Vallee Poussin(1866-1962)) that the density of primes is ruled by the lawp(n) ~ nlog(n)where the prime counting function p(n) is the number of primenumbers less than a given integer n. This result proved in 1896 is thecelebrated prime numbers theorem and was conjectured earlier, in 1792, by youngCarl Friedrich Gauss (1777-1855) and by Adrien-Marie Legendre (1752-1833) whostudied the repartition of those numbers in published tables of primes.This approximation may be usefully replaced by the more accuratelogarithmic integral Li(n):p(n) ~ Li(n)=óõn2 dtlog(t).However among the deeply studied set of primes there is a famous andfascinating subset for which very little is known and has generated somefamous conjectures: the twin primes (the term prime pairswas used before [5]). Definition 1 A couple of primes (p,q) are said to be twins if q=p+2. Except for thecouple (2,3), this is clearly the smallest possible distance between two primes. Example 2 (3,5),(5,7),(11,13),(17,19),(29,31),...,(419,421),... are twin primes. 2 Counting twin primesAs for the set of primes the most natural question is wether the set of twinprimes is finite or not. But unlike prime numbers for which numerous andelementary proofs exist [10], the answer to this natural questionis still unknown for twin primes ! Today, this problem remains one of thegreatest challenge in mathematics and has occupied numbers of mathematicians.Of course, as we will see, there are some empirical and numerical resultssuggesting an answer and most mathematicians believe that there are infinitelymany twin primes.In 1849, Alphonse de Polignac (1817-1890) made the general conjecture thatthere are infinitely many primes distant from 2k. The case for which k=1is the twin primes case.It's now natural to introduce the twin prime counting functionp2(n) which is the number of twin primes smaller than a given n. 2.1 Numerical resultsUsing huge table of primes (Glaisher 1878 [5], before computerage, enumerated p2(105)) and with intensive computations duringmodern period (Shanks and Wrench 1974 [12], Brent 1976 [1],Nicely 1996-2002 [9], Sebah 2001-2002 [11], see also[10]) it's possible to compute the exact values of p2(n)for large n and its conjectured approximation 2C2Li2(n) (see nextsection for the definition).The following array includes the relative error e (in %) betweenthe approximation and the real value.n p2(n) 2C2Li2(n) e10 2 5 150.00102 8 14 75.00103 35 46 31.43104 205 214 4.39105 1224 1249 2.04106 8169 8248 0.97107 58980 58754 -0.38108 440312 440368 0.013109 3424506 3425308 0.0231010 27412679 27411417 -0.00461011 224376048 224368865 -0.00321012 1870585220 1870559867 -0.00131013 15834664872 15834598305 -0.000421014 135780321665 135780264894 -0.0000421015 1177209242304 1177208491861 -0.0000641016 10304195697298 10304192554496 -0.000031At present time (2002), Pascal Sebah has reached p2(1016) and hisvalues are confirmed by Thomas Nicely up to p2(4.1015) who used anindependent approach and implementation. 2.1.1 Sieving twin primesBecause the most convenient (in fact the only available) way to computep2(n) is to find all twin primes and just count them, it's of greatimportance to improve as much as possible such an algorithm. All known methodsuse variations on the historical Eratosthenes sieve.In order to accelerate the sieve, a possible idea is to represent integersmodulo a base m, so that any integer has the form mk+r with 0 £ r < m.Primes numbers are such as m and r are relatively primes and for any valueof m, there are f(m) numbers r which are prime with m (this is thedefinition of Euler's f totient function).Modulo 6 For example modulo 6 all integers have one of the form6k,6k+1,6k+2,6k+3,6k+4,6k+5but 6k may not be prime, 6k+2 and 6k+4 are divisible by 2, 6k+3 isdivisible by 3, therefore primes (except 2 and 3) must be of the form6k+1,6k+5or which is more convenient to sieve twin primes( 6k+5,6k+7) .This allows to sieve a proportion of only f(m)/m=2/6 or 33.3% of allthe numbers.Modulo 30 The same kind of approach modulo 30 gives for candidates30k+1,30k+7,30k+11,30k+13,30k+17,30k+19,30k+23,30k+29and here we need to sieve only f(m)/m=8/30 or 26.66% of the integersto find all primes (except 2,3 and 5).But remember that we are only trying to sieve twin primes hence are left onlythe candidate couples( 30k+11,30k+13) ,( 30k+17,30k+19) ,(30k+29,30k+31)and the proportion drops to 6/30 or 20% of all integers.This suggest to introduce the function f2(m) which is the number ofpairs of integer 0 £ r < m such as r and r+2 are relatively prime withm. We observe from the last two examples thatf2(6)=1,f2(30)=3. Example Let's illustrate this on a numerical example. The enumeration of twin primesmodulo 30 up to 1010 gives, respectively, for each of the 3 previouscouples:9137078,9138015,9137584twin primes. So that (don't forget to count the two couples (3,5) and(5,7)!)p2(1010)=9137078+9138015+9137584+2=27412679. And, for the same couples, up to 1012:623517830,623557143,623510245which producesp2(1012)=623517830+623557143+623510245+2=1870585220.It's interesting to observe that the contribution to the enumeration of thetwin primes of each couple is almost equivalent. This was also observed duringall numerical estimations for other modulo like 210, 2310, 30030, ...[11].This result is well known when enumerating just prime numbers but may beconjectured for twin primes.Other modulo In this table we show the proportion 2f2(m)/m of integer to sieve inorder to count twin primes as a function of the modulo m:m f2(m) %2 . 50.06 1 33.330 3 20.0210 15 14.32310 135 11.730030 1485 9.9510510 22275 8.7The smallest ratios are obtained for values of m which are the product ofthe first primes (2#=2,3#=2×3,5#=2×3×5,7#=2×3×5×7,...), that is the first values of the primorial #function. For example in [11], the sieves were made modulo 30030and 510510, therefore less than 10% of the set of integers were consideredby the algorithm. In some others implementations sieves modulo 6 or 30 are used. 2.2 Twin prime conjectureBased on heuristic considerations, a law (the twin prime conjecture)was developed, in 1922, by Godfrey Harold Hardy (1877-1947) and John EdensorLittlewood (1885-1977) to estimate the density of twin primes.According to the prime number theorem the probability that a numbern is prime is about 1/log(n), therefore, if the probability that n+2 isalso prime was independent of the probability for n, we should have theapproximationp2(n) ~ nlog2(n),but a more careful analysis shows that this model is too simplified (anargument is given in [6]). In fact we have the following and moreaccurate conjecture (called conjecture B in[7]). Conjecture 3 [Twin prime conjecture]For large values of n, the two following equivalentapproximations are conjecturedp2(n) ~ 2C2Li2(n)=2C2óõn2 dtlog2(t)(1)orp2(n) ~ 2C2 nlog2(n)(2)Note that C2 is the twin prime constant and is defined byC2=Õp ³ 3 æè p(p-2)(p-1)2öø=0.6601618158468695739278121100145...This last constant occurs in some asymptotic estimations involving primes andit's interesting to observe that it may be estimated using properties of theRiemann Zeta function to thousand of digits (Sebah computed it tomore than 5000 digits). Figure 1: p2(n) and 2C2Li2(n) Remark 4 The function Li2(n) occuring in (1) may be related to thelogarithmic integral Li(n) by the trivial relationLi2(n)=Li(n)+ 2log(2)- nlog(n). 2.2.1 GeneralizationsIn fact, Hardy and Littlewood made a more general conjecture on the primesseparated by a gap of d. A natural generalization of the twin primes is tosearch for primes distant of d=2k (which should be infinite for any daccording to Polignac's conjecture). The case d=2 is the twin primes set,d=4 forms the cousin primes set, d=6 is the y primes set, ...If we denote pd(n) the number of primes p £ n such as p+d is alsoprime (observe that here p and p+d may not be consecutive),Hardy-Littlewood's conjecture states (in [7]) that ford ³ 2:pd(n) ~ 2C2Rdóõn2 dtlog2(t),with Rd ³ 1 being the rational numberRd=Õp|d,p > 2 p-1p-2, p is prime.The first values of the function Rd ared 2 4 6 8 10 12 14 16 18 20Rd 1 1 2 1 4/3 2 6/5 1 2 4/3According to this conjecture the density of twin primes is equivalent to thedensity of cousin primes. For example, the exact computed values up to1012 are: p2(1012) =1870585220p4(1012) =1870585458, which can be compared to the predicted value 1870559867 by the conjecture.Marek Wolf has studied the functionW(n)=p2(n)-p4(n)and its fractal properties and approximate dimension of 1.48 ([13]). 3 Brun's constant 3.1 From Euler's constant to Brun's constantEuler's constant It's very natural to understand the nature of the harmonic numbersH(n)=1+ 12+ 13+ 14+...+ 1nwhen n becomes large and the sum takes all integers in account. We knowsince Euler, for instance, thatêêêH(n) ~ log(n)H(n)-log(n) ~ gso that the harmonic numbers tends to infinite like log(n). Note thatg is Euler's constant and may be evaluated to million of digits.Mertens' constant The next step is to take in account only the primes numbers in the sum thatisP(p)=1+ 12+ 13+ 15+...+ 1pand we have the beautiful results thatêêêP(p) ~ log( log(p)) P(p)-log( log(p)) ~ MTherefore the sum diverges (this was also observed by Euler) but at the very low rate log(log(p)) and M is the interesting Mertens' constant which may beevaluated to much less digits than g, say a few thousands.Brun's Constant In the last step we only take in account the twin primes less than p in thesumB2(p)=æè 13+ 15öø+æè 15+ 17öø+æè 111+ 113öø+...and here comes the remarkable result due to Norwegian Mathematician Viggo Brun(1885-1978) in 1919 [2]. Theorem 5 The sum of the inverse of the twin primes converges to a finite constantB2.We write this result aslimp®¥ B2(p)=B2.Note that this theorem doesn't answer to the question of the infinitude oftwin primes, it just says that the limit exists (and may or may not contains afinite number of terms !). The proof is rather complex and based on amajoration of the density of twin primes ; a more modern one may also be foundin [8].Unlike Euler's constant or Mertens' constant, Brun's constant is one of thehardest to evaluate and we are not even sure to know 9 digits of it. By meanof very intensive computations, we only have guaranteed minorations ! 3.2 Estimation of Brun's constant 3.2.1 Direct estimationIn the following table we have try to estimate this constant by computing thepartial sums B2(p) up to different values of p.p B2(p) 102 1.330990365719...104 1.616893557432...106 1.710776930804...108 1.758815621067...1010 1.787478502719...1012 1.806592419175...1014 1.820244968130...1015 1.825706013240...1016 1.830484424658...From this, we observe that the convergence is extremely slow and irregular. Ifwe expect to find even just a few digits, we have to make some assumptions. 3.2.2 ExtrapolationAn easy consequence of the twin prime conjecture is that we may write thenumbers B2(p) as (see [4] and [9])B2(p)=B2- 4C2log(p)+Oæè 1Öplog(p)öøand thanks to this relation, the extrapolated valueB2*(p)=B2(p)+ 4C2log(p)converges much faster to Brun's constant B2.Let's take a look to numerical values:p B2*(p) 102 1.904399633290...104 1.903598191217...106 1.901913353327...108 1.902167937960...1010 1.902160356233...1012 1.902160630437...1014 1.902160577783...1015 1.902160582249...1016 1.902160583104...which suggest that the value of B2 should be around 1.902160583... (asimilar value was first proposed by Nicely after intensive computations andchecked later by Sebah, see [9] and [11]).The relationB2(p) ~ B2- 4C2log(p)invites us to draw the function B2(p)=f( 1/log(p)) (seeFigure 2) which should be a line with a negative slop with a valuenear -4C2 » -2.64064726. Figure 2: B2(p)=f( [ 1/log(p)]) The intersection of the line with the vertical axis (that is p=¥) isBrun's constant if the twin prime conjecture is valid. And according to thisline the direct estimation B2(p) should reach 1.9 not before the valuep ~ 10530 which is far beyond any computational project ! 4 Twin prime characterizationThere is a result from Clement (1949, [3]) which permits to see ifa couple (p,p+2) is a twin primes pair. This theorem extends Wilson's famoustheorem on prime numbers. Theorem 6 Let p ³ 3, the integers (p,p+2) form a twin primes pair if and only if4( (p-1)!+1) º -p mod p(p+2) Example 7 For p=17, 4( (p-1)!+1) = 83691159552004 º 306 mod 323 and-p º 306 mod 323, therefore (17,19) is a twin prime pair.The huge value of the factorial makes this theorem of no practical use to findlarge twin primes. 4.1 Large twin primesToday, thanks to modern computers, a lot of huge twin primes are known. Manyof those primes are of the form k×2n±1 because there are efficientprimality testing algorithms for such numbers when k is not too large.The following theorem due to the French farmer François Proth (1852-1879)may be used. Theorem 8 [Proth's theorem - 1878]Let N=k.2n+1 with k < 2n, if there is aninteger a such asa(N-1)/2 º -1 mod Nthen N is prime.To help finding large pairs, an idea is to take a value for n and then tostart a sieve in order to reduce the set of possible values for the k. Itshould take a few hours to find twin primes with a few thousands digits.For example the following numbers are twin prime pairs (some are given from[10]): 459.28529±1 Dubner, 1993 594501.29999±1 6797727.215328±1 Forbes, 1995 697053813.216352±1 Indlekofer & Janai, 1994 318032361.2107001±1 Underbakke & Carmody & ..., 2001 The last one is a twin primes pair of more than 32000 digits !References [1]R.P. Brent, Tables Concerning Irregularities in theDistribution of Primes and Twin Primes Up to 1011, Math. Comput.,(1976), vol. 30, p. 379 [2]V. Brun, La série1/5+1/7+1/11+1/13+1/17+1/19+1/29+1/31+1/41+1/43+1/59+1/61+..., où lesdénominateurs sont nombres premiers jumeaux est convergente ou finie,Bulletin des sciences mathématiques, (1919), vol. 43, p. 100-104 and p. 124-128 [3]P.A. Clement, Congruences for sets of primes, AmericanMathematical Monthly, (1949), vol. 56, p. 23-25 [4]C.E. Fröberg, On the sum of inverses of primes andtwin primes, Nordisk Tidskr. Informationsbehandling (BIT), (1961), vol. 1, p. 15-20. [5]J.W.L. Glaisher, An enumeration of prime-pairs,Messenger of Mathematics, (1878), vol. 8, p. 28-33 [6]G.H. Hardy and E. M. Wright, An Introduction to theTheory of Numbers, Oxford Science Publications, (1979) [7]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 Mathematica, (1922), vol. 44, p. 1-70 [8]W.J. LeVeque, Fundamentals of Number Theory, New York,Dover, (1996) [9]T. Nicely, Enumeration to 1014 of the TwinPrimes and Brun's Constant, Virginia J. Sci., (1996), vol. 46, p. 195-204 [10]P. Ribenboim, The new Book of Prime Number Records,Springer, (1996) [11]P. Sebah, Counting Twin Primes and estimation ofBrun's Constant up to 1016, Computational project athttp://numbers.computation.free.fr/Constants/constants.html, (2002) [12]D. Shanks and J.W. Wrench, Brun's Constant, (1974),Math. Comput., vol. 28, p. 293-299 [13]M. Wolf, On the Twin and Cousin primes, (1996), Seehttp://www.ift.uni.wroc.pl/~mwolf/File translated fromTEXby TTH,version 3.01.On 29 Jul 2002, 14:41. |
|
