Introduction to twin primes and Brun’s constantcomputation
Pascal Sebah and Xavier Gourdon
numbers.computation.free.fr/Constants/constants.html
July 30, 2002
Abstract
An introduction to the set of twin primes, to a sieving method to countthem and to the latest estimation of Brun’s constant.

1

Introduction

It’s a very old fact (Euclid 325-265 B.C., in Book IX of the Elements) that theset 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)) thatthe density of primes is ruled by the law
π(n) ∼nlog(n)

where the prime counting function π(n) is the number of prime numbers lessthan a given integer n. This result proved in 1896 is the celebrated prime numbers theorem and was conjectured earlier, in 1792, by young Carl Friedrich Gauss(1777-1855) and in 1798 by Adrien-Marie Legendre (1752-1833) who studied therepartition of those numbers in published tables of primes.
This approximation may be usefully replaced by the more accurate logarithmic integral Li(n):Z ndt
π(n) ∼ Li(n) =.
log(t)
2
However among the deeply studied set of primes there is a famous and fascinating subset for which very little is known and has generated some famous
conjectures: the twin primes (the term prime pairs was used before [5]).
Definition 1 A couple of primes (p, q) are said to be twins if q = p + 2. Except
for the couple (2, 3), this is clearly the smallest possible distance between twoprimes.
Example 2 (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), ..., (419, 421), ... are twin primes.
12Counting twin primes

As for the set of primes the most natural question is wether the set of twin
primes is finite or not. But unlike prime numbers for which numerous andelementary proofs exist [10], the answer to this natural question is still unknown
for twin primes ! Today, this problem remains one of the greatest challenge inmathematics and has occupied numbers of mathematicians. Of course, as wewill see, there are some empirical and numerical results suggesting an answer
and most mathematicians believe that there are infinitely many twin primes.
In 1849, Alphonse de Polignac (1817-1890) made the general conjecture that
there are infinitely many primes distant from 2k. The case for which k = 1 isthe twin primes case.
It’s now natural to introduce the twin prime counting function π2 (n) whichis the number of twin primes smaller than a given n.

2.1

Numerical results

Using huge table of primes (Glaisher 1878 [5], before computer age, enumerated
π2 (105 )) and with intensive computations during modern period (Shanks andWrench 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 π2 (n) for large n andits conjectured approximation 2C2 Li2 (n) (see next section for the definition).
The following array includes the relative error ε (in %) between the approximation and the real value.
n10
102
103
104
105
106
107
108
109
1010
1011
1012
1013
1014
1015
1016

π2 (n)
28
35
205
1224
8169
58980
4403123424506
27412679
224376048
1870585220
15834664872
135780321665
1177209242304
10304195697298

2C2 Li2 (n)
514
46
214
1249
8248
58754
440368342530827411417
224368865
1870559867
15834598305
135780264894
1177208491861
10304192554496

ε150.00
75.00
31.43
4.39
2.04
0.97
−0.38
0.013
0.023
−0.0046−0.0032−0.0013−0.00042−0.000042−0.000064−0.000031

At present time (2002), Pascal Sebah has reached π2 (1016 ) and his values
are confirmed by Thomas Nicely up to π2 (4.1015 ) who used an independent
approach and implementation.

22.1.1

Sieving twin primes

Because the most convenient (in fact the only available) way to compute π2 (n) isto find all twin primes and just count them, it’s of great importance to improveas much as possible such an algorithm. All known methods use variations on
the historical Eratosthenes sieve.
In order to accelerate the sieve, a possible idea is to represent integers modulo
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 value of m, there
are φ(m) numbers r which are prime with m (this is the definition of Euler’s φtotient function [6]).
Modulo 6

For example modulo 6 all integers have one of the form
6k, 6k + 1, 6k + 2, 6k + 3, 6k + 4, 6k + 5

but 6k may not be prime, 6k + 2 and 6k + 4 are divisible by 2, 6k + 3 is divisible
by 3, therefore primes (except 2 and 3) must be of the form
6k + 1, 6k + 5
or which is more convenient to sieve twin primes(6k + 5, 6k + 7) .
This allows to sieve a proportion of only φ(m)/m = 2/6 or 33.3% of all thenumbers.
Modulo 30

The same kind of approach modulo 30 gives for candidates

30k + 1, 30k + 7, 30k + 11, 30k + 13, 30k + 17, 30k + 19, 30k + 23, 30k + 29
and here we need to sieve only φ(m)/m = 8/30 or 26.66% of the integers to findall primes (except 2,3 and 5).
But remember that we are only trying to sieve twin primes hence are left
only the 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 φ2 (m) which is the number of pairs ofinteger 0 ≤ r < m such as r and r + 2 are relatively prime with m. We observefrom the last two examples that
φ2 (6) = 1, φ2 (30) = 3.

3

Example Let’s illustrate this on a numerical example. The enumeration oftwin primes modulo 30 up to 1010 gives, respectively, for each of the 3 previous
couples:
9137078, 9138015, 9137584
twin primes. So that (don’t forget to count the two couples (3, 5) and (5, 7)!)π2 (1010 ) = 9137078 + 9138015 + 9137584 + 2 = 27412679.
And, for the same couples, up to 1012 :
623517830, 623557143, 623510245
which produces
π2 (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 during
all 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 2φ2 (m)/m of integer tosieve in order to count twin primes as a function of the modulo m:m
26302102310
30030
510510φ2 (m)
.
1
3
15
135
1485
22275

%
50.0
33.3
20.0
14.3
11.7
9.9
8.7

The smallest ratios are obtained for values of m which are the product of
the 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], thesieves were made modulo 30030 and 510510, therefore less than 10% of the setof integers were considered by the algorithm. In some others implementations
sieves modulo 6 or 30 are used.

2.2

Twin prime conjecture

Based on heuristic considerations, a law (the twin prime conjecture) was developed, in 1922, by Godfrey Harold Hardy (1877-1947) and John Edensor Littlewood (1885-1977) to estimate the density of twin primes.
4According to the prime number theorem the probability that a number n isprime is about 1/ log(n), therefore, if the probability that n + 2 is also primewas independent of the probability for n, we should have the approximation
π2 (n) ∼n,log2 (n)but a more careful analysis shows that this model is too simplified (an argumentis given in [6]). In fact we have the following and more accurate conjecture(called conjecture B in[7]).
Conjecture 3 (Twin prime conjecture) For large values of n, the two following equivalent approximations are conjectured
Z ndt
π2 (n) ∼ 2C2 Li2 (n) = 2C2(1)22 log (t)orπ2 (n) ∼ 2C2nlog2 (n)(2)

Note that C2 is the twin prime constant and is defined by
Y µ p(p − 2) ¶C2 == 0.6601618158468695739278121100145...
(p − 1)2p≥3

This new constant occurs in some asymptotic estimations involving primes
and it’s interesting to observe that it may be estimated using properties of theRiemann Zeta function to thousand of digits (Sebah computed it to more than
5000 digits).
Remark 4 The function Li2 (n) occuring in (1) may be related to the logarithmic integral Li(n) by the trivial relation
Li2 (n) = Li(n) +2.2.12n−.
log(2) log(n)Generalizations

In fact, Hardy and Littlewood made a more general conjecture on the primes
separated by a gap of d. A natural generalization of the twin primes is to searchfor primes distant of d = 2k (which should be infinite for any d according toPolignac’s conjecture). The case d = 2 is the twin primes set, d = 4 forms thecousin primes set, d = 6 is the sexy primes set, ...
If we denote πd (n) the number of primes p ≤ n such as p + d is also prime(observe that here p and p + d may not be consecutive), Hardy-Littlewood’s
conjecture states (in [7]) that for d ≥ 2:Z ndt,πd (n) ∼ 2C2 Rd2log(t)2512001000
800600400200020000

40000 n 60000

80000

100000Figure 1: π2 (n) and 2C2 Li2 (n)with Rd ≥ 1 being the rational numberY

Rd =p|d,p>2

p−1,p−2

p is prime.

The first values of the function Rd aredRd2
14
1

62

8
1

10
4/3

122

14
6/5

16118
2

20
4/3

According to this conjecture the density of twin primes is equivalent to thedensity of cousin primes. For example, the exact computed values up to 1012are:
π2 (1012 ) = 1870585220
π4 (1012 ) = 1870585458,
which can be compared to the predicted value 1870559867 by the conjecture.
Marek Wolf has studied the function
W (n) = π2 (n) − π4 (n)and its fractal properties and approximate dimension of 1.48 ([13]).

6

3Brun’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
numbers
1 1 1
1H(n) = 1 + + + + ... +2 3 4n
when n becomes large and the sum takes all integers in account. We know sinceEuler, for instance, that¯¯ H(n) ∼ log(n)¯¯ H(n) − log(n) ∼ γ
so that the harmonic numbers tends to infinite like log(n). Note that γ 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 that isP (p) = 1 +1 1 1
1+ + + ... +2 3 5p

and we have the beautiful results that¯¯ P (p) ∼ log (log(p))¯¯ P (p) − log (log(p)) ∼ M
Therefore the sum diverges (and this was also observed by Euler) but at thevery low rate log (log(p)) and M is the interesting Mertens’ constant which may
be evaluated to much less digits than γ, say a few thousands.
Brun’s Constant In the last step we only take in account the twin primes
less than p in the sumµ¶ µ¶ µ¶1 11 111
B2 (p) =++++++ ...
3 55 7
11 13and 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
constant B2 .
We write this result as
lim B2 (p) = B2 .

p→∞

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 a7

finite number of terms !). The proof is rather complex and based on a majorationof the density of twin primes ; a more modern one may also be found in [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 mean ofvery intensive computations, we only have guaranteed minorations !

3.2

Estimation of Brun’s constant

3.2.1

Direct estimation

In the following table we have try to estimate this constant by computing thepartial sums B2 (p) up to different values of p.
p
102
104
106
108
1010
1012
1014
1015
1016

B2 (p)
1.330990365719...
1.616893557432...
1.710776930804...
1.758815621067...
1.787478502719...
1.806592419175...
1.820244968130...
1.825706013240...
1.830484424658...

From this, we observe that the convergence is extremely slow and irregular.
If we expect to find even just a few digits, we have to make some assumptions.
3.2.2

Extrapolation

An easy consequence of the twin prime conjecture is that we may write thenumbers B2 (p) as (see [4] and [9])µ¶4C2
1B2 (p) = B2 −+O √log(p)p log(p)and thanks to this relation, the extrapolated value
B2∗ (p) = B2 (p) +4C2log(p)converges much faster to Brun’s constant B2 .
Let’s take a look to numerical values:

8

1.9

1.8

1.7

1.6

1.5 0

0.02 0.04 0.06 0.08

0.1 0.12 0.14 0.16
³Figure 2: B2 (p) = fp102
104
106
108
1010
1012
1014
1015
1016

1log(p)´

B2∗ (p)1.904399633290...
1.903598191217...
1.901913353327...
1.902167937960...
1.902160356233...
1.902160630437...
1.902160577783...
1.902160582249...
1.902160583104...

which suggest that the value of B2 should be around 1.902160583... (a similarvalue was first proposed by Nicely after intensive computations and checked laterby Sebah, see [9] and [11]).
The relation
4C2
B2 (p) ∼ B2 −log(p)
invites us to draw the function B2 (p) = f (1/ log(p)) (see Figure 2) which should
be a line with a negative slop with a value near −4C2 ≈ −2.64064726.
The intersection of the line with the vertical axis (that is p = ∞) is Brun’s
constant if the twin prime conjecture is valid. And according to this line thedirect estimation B2 (p) should reach 1.9 not before the value p ∼ 10530 which
is far beyond what could be reach with any computer!
9

4Twin prime characterization

There is a result from Clement (1949, [3]) which permits to see if a couple(p, p + 2) is a twin primes pair. This theorem extends Wilson’s famous theorem
on prime numbers.
Theorem 6 Let p ≥ 3, the integers (p, p + 2) form a twin primes pair if andonly 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 tofind large twin primes.

4.1

Large twin primes

Today, 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 efficient primality
testing algorithms for such numbers when k is not too large.
The following theorem due to the French farmer François Proth (1852-1879)
may be used.
Theorem 8 (Proth’s theorem - 1878) Let N = k.2n + 1 with k < 2n , ifthere is an integer a such asa(N −1)/2 ≡ −1 mod N
then N is prime.
To help finding large pairs, an idea is to take a value for n and then to starta sieve in order to reduce the set of possible values for the k. It should take afew hours to find twin primes with a few thousands digits.
For example the following numbers are twin prime pairs (some are givenfrom [10]):459.28529

Dubner, 1993

9999

594501.2

6797727.215328

Forbes, 1995

16352

Indlekofer & Janai, 1994

107001

Underbakke & Carmody & ..., 2001

697053813.2
318032361.2

The last one is a twin primes pair of more than 32000 digits !

10References[1] R.P. Brent, Tables Concerning Irregularities in the Distribution of Primes
and Twin Primes Up to 1011 , Math. Comput., (1976), vol. 30, p. 379[2] V. Brun, La sé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+...,où les dénominateurs sont nombres premiers jumeaux est convergente ou
finie, Bulletin des sciences mathématiques, (1919), vol. 43, p. 100-104 andp. 124-128[3] P.A. Clement, Congruences for sets of primes, American Mathematical
Monthly, (1949), vol. 56, p. 23-25[4] C.E. Fröberg, On the sum of inverses of primes and twin 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 the Theory 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 Twin Primes 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)
Sebah,Counting
Twin
Primesandestimation[11] P.
Brun’sConstant
upto1016 ,Computational
project
http://numbers.computation.free.fr/Constants/constants.html, (2002)

ofat[12] D. Shanks and J.W Wrench, Brun’s Constant, (1974), Math. Comput., vol.
28, p. 293-299[13] M. Wolf, On the Twin andhttp://www.ift.uni.wroc.pl/˜mwolf/

11

Cousinprimes,(1996),

See