On the First Occurrences of Gaps Between Primes in a Residue Class

Alexei Kourbatov JavaScripter.net Redmond, WA 98052 USA

                 akourbatov@gmail.com

Marek Wolf Faculty of Mathematics and Natural Sciences Cardinal Stefan Wyszyński University Warsaw, PL-01-938 Poland

                  m.wolf@uksw.edu.pl

To the memory of Professor Thomas R. Nicely (1943–2019)

Abstract

We study the first occurrences of gaps between primes in the arithmetic progression (P): r, r + q, r + 2q, r + 3q, …, where q and r are coprime integers, q > r ≥ 1. The growth trend and distribution of the first-occurrence gap sizes are similar to those of maximal gaps between primes in (P). The histograms of first-occurrence gap sizes, after appropriate rescaling, are well approximated by the Gumbel extreme value distribution. Computations suggest that first-occurrence gaps are much more numerous than maximal gaps: there are O(log^{2} x) first-occurrence gaps between primes in (P) below x, while the number of maximal gaps is only O(log x). We explore the connection between the asymptotic density of gaps of a given size and the corresponding generalization of Brun’s constant. For the first occurrence of gap d in (P), we expect the end-of-gap prime p ≍ \sqrt{d} exp(\sqrt{d/φ(q)}) infinitely often. Finally, we study the gap size as a function of its index in the sequence of first-occurrence gaps.

1 Introduction

Let p_{n} be the n-th prime number, and consider the difference between successive primes, called a prime gap: p_{n+1} −p_{n}. If a prime gap is larger than all gaps before it, we call this gap maximal. If a prime gap is either larger or smaller than (but not equal to) any gap before it, we call this gap a first occurrence [4, 22, 25, 27, 43].

Let G(x) be the largest gap between primes ≤ x:

G(x) = max_{p_{n+1}≤x}(p_{n+1} − p_{n}).

A lot has been conjectured about large prime gaps; much less has been rigorously proved. Today’s best known results on the growth of G(x) as x → ∞ are as follows:

A \frac{log x log log x log log log log x}{log log log x} < G(x) < Bx^{0.525},

with some positive constants A and B. The upper bound is due to Baker, Harman, and Pintz [1], and the lower bound to Ford, Green, Konyagin, Maynard, and Tao [8]. Computations suggest that the above double inequality holds with A = B = 1 for all x ≥ 153, while the lower bound holds with A = 1 wherever the left-hand side expression is defined; cf. [10].

The notion of prime gap admits a natural generalization. Given an increasing integer sequence (S), we can consider gaps p′ − p between primes p and p′ both of which are in (S), under the condition that p < p′ and there are no other primes in (S) between p and p′. Maximal gaps and first occurrence gaps between primes in (S) are also defined in a natural way, similar to the above.

In our recent work [19] we investigated the statistical properties of maximal gaps in certain increasing subsequences of the prime numbers. In this paper we turn our attention to a related, more numerous family of prime gaps: the first occurrences of gaps of a particular size. As a sequence (S) of interest, here we will choose an arithmetic progression (P): r + nq, n = 0, 1, 2, 3, …, with gcd(q, r) = 1. It is plain that the first-occurrence gaps include, as a subsequence, all maximal gaps between primes p ≡ r (mod q); e.g., sequences \underline{A268925} and \underline{A330853} from the On-Line Encyclopedia of Integer Sequences (OEIS) [37] illustrate the case q = 6, r = 1. We will see that maximal gaps and first-occurrence gaps between primes in (P) share certain statistical properties.

If we limit ourselves to studying the maximal and first-occurrence gaps in the sequence of all primes, we will find that the available data are quite scarce. As of 2019, we know only 745 first-occurrence gaps between primes below 2^{64} (OEIS \underline{A014320}); of these first occurrences, only 80 gaps are maximal [24]. This is one of the compelling reasons to study large gaps between primes in residue classes, i.e., in arithmetic progressions (P): r + nq. If the value of q used as the common difference of progression (P) is “not too small”, we get plenty of data to study large prime gaps. That is, we get many sequences of first-occurrence gaps corresponding to progressions r + nq, for the same fixed q, which enables us to focus on common features of these sequences. One such feature is the common histogram of (appropriately rescaled) sizes of first-occurrence gaps. Other interesting features are the average numbers of maximal gaps and first-occurrence gaps between primes in (P) not exceeding x.

1.1 Notation

p_{n}  the n-th prime; {p_{n}} = {2, 3, 5, 7, 11, …}
q, r  coprime integers, 1 ≤ r < q
(P) = (P)_{q,r}  the arithmetic progression r, r + q, r + 2q, r + 3q, …
P_{f}(d; q, r)  the prime starting the first occurrence of gap d between primes in (P)
P′_{f}(d; q, r)  the prime ending the first occurrence of gap d between primes in (P)
p_{f}(d)  the prime starting the first occurrence of gap d in the sequence of all primes
gcd(m, n)  the greatest common divisor of m and n
lcm(m, n)  the least common multiple of m and n
⌊x⌋  the floor function: the greatest integer ≤ x
⌈x⌉  the ceiling function: the least integer ≥ x
φ(q)  Euler’s totient function (OEIS \underline{A000010})
f(x) ∼ h(x)  f(x)/h(x) → 1 as x → ∞
f(x) ≍ h(x)  Ah(x) ≤ f(x) ≤ Bh(x) for some A, B > 0
f(x) ≲ h(x)  f(x) ∼ h(x) and f(x) < h(x) for large x
A ≈ B  A is close to B (the ≈ relation is often based on heuristics or numerical data)
Gumbel(x; α, μ) the Gumbel distribution cdf: Gumbel(x; α, μ) = e^{−e^{− \frac{x−μ}{α}}}
Exp(x; α)  the exponential distribution cdf: Exp(x; α) = 1 − e^{−x/α}
α  the scale parameter of exponential/Gumbel distributions, as applicable
μ  the location parameter (mode) of the Gumbel distribution
γ  the Euler–Mascheroni constant: γ = 0.57721 … (OEIS \underline{A001620})
Π_{2}  the twin prime constant: Π_{2} = 0.66016 … (OEIS \underline{A005597}; Π_{2}^{−1} is \underline{A167864})
log x  the natural logarithm of x
li x  the logarithmic integral of x: li x = ∫_{0}^{x} \frac{dt}{log t} = ∫_{2}^{x} \frac{dt}{log t} + 1.04516 …

Prime counting functions:

π(x)  the total number of primes p_{n} ≤ x
π(x; q, r)  the total number of primes p = r + nq ≤ x

Gap counting functions:

N_{q,r}(x)  the number of maximal gaps G_{q,r} in (P) with endpoints p ≤ x
N′_{q,r}(x)  the number of first-occurrence gaps in (P) with endpoints p ≤ x
τ_{q,r}(d, x)  the number of gaps of a given even size d = p′ − p between successive

primes p, p′ ≡ r (mod q), with p′ ≤ x; τ_{q,r}(d, x) = 0 if q ∤ d or 2 ∤ d. Gap measure functions:

G(x)  the maximal gap between primes ≤ x: G(x) = max_{p_{n+1}≤x}(p_{n+1} − p_{n})
G_{q,r}(x)  the maximal gap between primes p = r + nq ≤ x
d_{q,r}(x)  the latest first-occurrence gap between primes p = r + nq ≤ x (sect. 3)
R(n, q, r)  size of the n-th record (maximal) gap between primes in (P) (sect. 7)
S(n, q, r)  size of the n-th first-occurrence gap between primes in (P) (sect. 7)
CSG ratio  the Cramér–Shanks–Granville ratio for gap p′ − p: CSG = \frac{p′−p}{φ(q) log^{2} p′}
a(q, x)  the expected average gap between primes in (P): a(q, x) = xφ(q)/ li x
T_{0}, T_{f}, T_{m}  trend functions predicting the growth of large gaps (sect. 2)

1.2 Preliminaries

The following theorems and conjectures provide a broader context for our work on large prime gaps.

The prime number theorem states that the number of primes not exceeding x is asymptotic to the logarithmic integral li x:

π(x) ∼ li x  as x → ∞.  (1)

The Riemann hypothesis implies that the error term in (1) is small:

π(x) − li x = O(x^{1/2+ε}) for any ε > 0;

that is, the numbers π(x) and ⌊li x⌋ almost agree in the left half of their digits. Let q > r ≥ 1 be fixed coprime integers, and consider the arithmetic progression

(P) r, r + q, r + 2q, r + 3q, ….

Dirichlet’s theorem on arithmetic progressions [7] establishes that there are infinitely many primes in progression (P) whenever gcd(q, r) = 1. The prime number theorem for arithmetic progressions [14] states that the number of primes in progression (P) not exceeding x is asymptotically equal to 1/φ(q) of the total number of primes ≤ x, that is,

π(x; q, r) ∼ \frac{π(x)}{φ(q)} ∼ \frac{li x}{φ(q)}  as x → ∞,  (2)

where φ(q) is Euler’s totient function. Under the Generalized Riemann Hypothesis [14, p. 253] we have

π(x; q, r) − \frac{li x}{φ(q)} = O(x^{1/2+ε}) for any ε > 0.

Polignac’s conjecture [29] states that every gap of an even size d = 2n, n ∈ ℕ, actually occurs between consecutive primes infinitely often. (In Section 4 we generalize Polignac’s conjecture to gaps of size n · lcm(2, q) between primes in progression (P); see Conjecture 5.)

Regarding the behavior of the function G(x)—the maximal prime gap up to x—Cramér conjectured in the 1930s that G(x) = O(log^{2} x) [6]; Shanks set forth a stronger hypothesis: G(x) ∼ log^{2} x [36]. Recent models [2, 12] cast doubt on the latter conjecture; we still consider it plausible in an “almost all” sense (for almost all maximal gaps).

Let G_{q,r}(x) denote the maximal gap between primes ≤ x in progression (P).

The Generalized Cramér conjecture states that almost all maximal gaps G_{q,r}(x) satisfy

G_{q,r}(x) < φ(q) log^{2} x.  [19, eq. (34)]  (3)

The Generalized Shanks conjecture is similar: almost all maximal gaps G_{q,r}(x) satisfy

G_{q,r}(x) ∼ φ(q) log^{2} x.  [19, eq. (35)]  (4)

2 The growth trend of large gaps

In this section we introduce three trend functions useful in describing the growth and distribution of large gaps between primes in arithmetic progression (P): r + nq. These trend functions are asymptotically equivalent to φ(q) log^{2} x and differ only in lower-order terms.

• The function T_{0}(q, x) is called a baseline trend. Roughly speaking, for large enough x, this trend curve separates typical sizes of maximal gaps from typical sizes of nonmaximal first-occurrence gaps; see sect. 2.1.

• The function T_{m}(q, x) will give us an estimate of the most probable maximal gap sizes. We have T_{m}(q, x) ≥ T_{0}(q, x); see sect. 2.2.

• The function T_{f}(q, x) will give us an estimate of the most probable first-occurrence gap sizes. For large x, we have T_{f}(q, x) < T_{0}(q, x); see sect. 2.3.

Motivated by the prime number theorem for arithmetic progressions (2), we give the following estimate a(q, x) of the average gap between primes in (P), to be used in trend functions.

Definition 1. The expected average gap between primes p ≤ x in progression (P) is

a(q, x) = \frac{xφ(q)}{li x},  (5)

where φ(q) is Euler’s totient function, and li x is the logarithmic integral.

2.1 The baseline trend T_{0}(q, x)

We now define a trend function that will play a central role in this work.

Definition 2. The baseline trend T_{0}(q, x) for large gaps between primes in (P) is

T_{0}(q, x) = a(q, x) log \frac{li x}{a(q, x)},  (6)

where a(q, x) is given by (5), and x is large enough, so that \frac{li x}{a(q,x)} > 1.

Formula (6) is a concise form of [19, eq. (33)] in which we set a constant term^{1} b = log φ(q). Thus, by definition we have

T_{0}(q, x) = \frac{xφ(q)}{li x} (2 log \frac{li x}{φ(q)} − log \frac{x}{φ(q)}) .  (7)

(Equations (6) and (7) can also be viewed as a generalization of the trend equation derived in [41, 42] for maximal prime gaps G(x), that is, for the particular case q = 2.)

1The choice of b = log φ(q) for use in [19, eq. (33)] reflects our heuristic expectation that, for large x, maximal gaps between primes ≤ x in (P) should depend primarily on the quantities φ(q), a(q, x), and π(x).

Moreover, this choice is supported by extensive numerical results; cf. [19, sect. 3.1].

Remark 3. The baseline trend T_{0} defined in (6) has the following properties:

(i) T_{0}(q, x) is a continuous and smooth function of x for every fixed q.

(ii) T_{0}(q, x) does not depend on the choice of r in progression (P).

(iii) T_{0}(q, x) does not use unknown parameters determined a posteriori.

By way of comparison, for exponentially distributed random (i.i.d.) intervals between rare events, with mean interval α and cdf Exp(ξ; α) = 1 − e^{−ξ/α}, the most probable maximal interval in [0, x] is about α log \frac{x}{α}. Note the absence of li x, in contrast to (6); cf. [13, sect. 4.1.1], [15, sect. 8], and [17, sect. 3.3].

Clearly, as x → ∞ we have

a(q, x) ≲ φ(q) log x,  (8)
T_{0}(q, x) ≲ φ(q) log^{2} x.  (9)

We numerically experimented with arithmetic progressions (P): r +nq for many different coprime pairs (q, r), up to q = 10^{5}. Invariably, we found that the majority of maximal gaps between primes ≤ x in (P) have sizes above the baseline trend curve T_{0}(q, x); that is, we usually have G_{q,r}(x) > T_{0}(q, x). At the same time, for large enough x, a significant proportion of non-maximal first-occurrence gap sizes are below the curve T_{0}(q, x). These findings hold at least for x ≤ 10^{14}.

2.2 The trend T_{m}(q, x) of maximal gaps

Most probable maximal gaps G_{q,r}(x) are close to the following trend [19, eqs. (33), (45)]:

T_{m}(q, x) = T_{0}(q, x) + E_{m}(q, x),  (10)

where the error term E_{m}(q, x) is nonnegative and given by this empirical formula:

E_{m}(q, x) ≈ \frac{b_{1} log φ(q)}{(log log x)^{b_{2}}} · a(q, x).  (11)

For q = 2, formula (11) gives E_{m}(2, x) = 0. Indeed, we found that the baseline trend T_{0}(2, x), even without an error term, satisfactorily describes the most probable sizes of maximal prime gaps G(x). (Another reasonably good choice of the error term in (10) for q = 2 is E_{m}(2, x) = ca(q, x) with a constant c ∈ [0, \frac{1}{2}].)

For q > 2, we found that the error term E_{m}(q, x) is positive, and it is best to determine b_{1} and b_{2} in (11) a posteriori. However, for x ∈ [10^{7}, 10^{14}] and q ∈ [10^{2}, 10^{5}], choosing

b_{1} = 4,  b_{2} = 2.7  (12)

yields a “good enough” trend curve for typical maximal gap sizes. This choice of b_{1}, b_{2} works best when q is prime or semiprime. See [17, 19] for further details on maximal gaps.

2.3 The trend T_{f}(q, x) of first-occurrence gaps

For the trend equation to better describe the most probable first-occurrence gap sizes, we add a lower-order correction term to the baseline trend (6):

T_{f}(q, x) = T_{0}(q, x) + E_{f}(q, x).  (13)

Based on extensive numerical data, we find that the term E_{f}(q, x) is eventually negative and given by this empirical formula:

E_{f}(q, x) ≈ (c_{0} − c_{1} log log x) · a(q, x),  (14)

where a(q, x) is defined by (5).

Like with T_{m}(q, x), it is best to determine the parameters c_{0} and c_{1} in (14) a posteriori. However, in some special cases, we were able to find predictive formulas for c_{0} and c_{1} as functions of q:

• If q is a prime ≥ 5, the following empirical formulas

c_{0} = c_{0}(q) ≈ 2.18 (log lcm(2, q))^{0.58},
c_{1} = c_{1}(q) ≈ 1.18 (log lcm(2, q))^{0.364} (15)

work well for parameters c_{0} and c_{1} in the term E_{f}(q, x) (14), for x ∈ [10^{7}, 10^{14}] and q ∈ [5, 10^{5}].

• If q is an even semiprime ≥ 10, it is plain that we deal with the same sequences of even first-occurrence gaps as above, so we can use the same formulas (15).

• For q = 2 (gaps in the sequence of all primes), the parameters

c_{0} ≈ 3,  c_{1} ≈ 1.58  (16)

are close to optimal in the term E_{f}(2, x), at least for x < 2^{64}.

2.4 Numerical results

Using PARI/GP [28] we performed computational experiments with progressions (P): r + nq for many different values of q ∈ [2, 10^{5}]. Figure 1 shows the sizes of first-occurrence gaps between primes in twenty progressions (P), for q = 211 and r ∈ [1, 20]. Results for other values of q look similar to Fig. 1. All our numerical results show that trend curves of the form (13), (14) satisfactorily describe the growth of typical first-occurrence gaps between primes in progressions (P).

Figure 1: First-occurrence gaps d_{q,r} between primes p = r+nq ≤ 10^{12} for q = 211, r ∈ [1, 20]. Dotted curve (•): trend T_{f} (13)–(15); blue dotted curve (^{♦}): baseline trend T_{0} (6); top line: y = φ(q) log^{2} p. The vast majority of maximal gaps stay above the curve T_{0}, while a growing proportion of non-maximal first-occurrence gaps are observed below T_{0}.

Figure 2: Histogram of rescaled values u (17) for the first-occurrence gaps between primes p = r + nq ∈ [10^{7}, 10^{12}] for q = 211 and all r ∈ [1, 210]. Bins: 53, bin size ≈ 0.23. Smooth curve: best-fit Gumbel distribution (pdf) with scale α = 0.87692 and mode μ = −0.00902.

3 The distribution of first-occurrence gap sizes

Extensive numerical data allows us to observe that typically a first-occurrence gap is also the largest gap between primes in the interval [x, x + x/(log x)^{1+ε}], for some ε > 0. This invites the question (cf. [15]–[20]): do first-occurrence gap sizes, after an appropriate rescaling transformation, obey the same distribution as maximal gap sizes—the Gumbel extreme value distribution?

Let d = d_{q,r}(x) denote the size of the first-occurrence gap between primes p ∈ [1, x]∩(P); specifically, the gap d_{q,r}(x) refers to the first occurrence closest to x on the interval [1, x]. Infinitely many distinct values of d_{q,r}(x) are maximal gaps, for which d_{q,r}(x) = G_{q,r}(x). At the same time, infinitely many distinct values of d_{q,r}(x) are not maximal gaps, and for these first occurrences we have d_{q,r}(x) < G_{q,r}(x).

3.1 Rescaling transformation

Extreme value theory motivates the following rescaling transformation (cf. [19, sect. 3.2]):

gap size d_{q,r}(x) ↦ u = \frac{d_{q,r}(x) − T_{f}(q, x)}{a(q, x)},  (17)

where a(q, x) is the expected average gap (5), T_{f}(q, x) is the trend function of first-occurrence gaps (13), and x runs through all end-of-gap primes in a given table of first-occurrence gaps. Every distinct gap size d_{q,r}(x) is counted only once and mapped to its rescaled value u.

Figure 2 shows a combined histogram of rescaled values u for first-occurrence gaps between primes in progressions (P) for q = 211 and all r ∈ [1, 210]. We can see at once that the histogram is skewed to the right. A good fit is the Gumbel extreme value distribution— which typically occurs in statistics as the distribution of maxima of i.i.d. random variables with an initial unbounded light-tailed distribution.

3.2 Distribution tails

Observe that the left tail of the histogram of rescaled gaps is light and short. That is, firstoccurrence gaps are never too far below their trend T_{f}(q, x); recall that the trend function T_{f}(q, x) itself is asymptotic to φ(q) log^{2} x. This leads us to the following

Conjecture 4. Let d_{q,r}(x) be the first-occurrence gap function defined above. Then

lim inf_{x→∞} \frac{d_{q,r}(x)}{φ(q) log^{2} x} = 1.

On the other hand, the right tail of the rescaled gaps histogram is long. For the sequence of all primes, Cramér’s model [6] suggests lim sup \frac{d_{2,1}(x)}{log^{2} x} = 1. Banks, Ford, and Tao [2] discuss models yielding a larger upper limit, 2e^{−γ} ≈ 1.1229; cf. Granville [12, p. 24].

3.3 Goodness of fit

For best-fit Gumbel distributions, we found that the Kolmogorov–Smirnov (KS) goodnessof-fit statistic was usually not much better (and sometimes worse) than the corresponding KS statistic measured for the data subset including maximal gaps only [19]. For example, the KS statistic for the histogram shown in Fig. 2 is 0.00815 (vs. 0.00628 for the corresponding data subset comprising maximal gaps only).

3.4 Distribution scale

For data sets containing all first occurrence gaps—as well as for maximal gaps only—the scale parameter α of best-fit Gumbel distributions was in the range α ∈ [0.7, 1]. In both cases, when we moved from smaller to larger end-of-gap primes, the scale α of best-fit Gumbel distributions appeared to slowly grow towards 1.

3.5 Beyond Gumbel

Among three-parameter distributions, a very good fit for first-occurrence gap histograms is the Generalized Extreme Value (GEV) distribution. Typical best-fit GEV distributions for rescaled values (17) have a small negative shape parameter, usually in the interval [−0.04, 0]. Recall that the Gumbel distribution is a GEV distribution whose shape parameter is exactly zero. From extreme value theory we also know that the GEV distribution of maxima with a negative shape parameter occurs for i.i.d. random variables with an initial distribution bounded from above.

On the other hand, if we fitted a GEV distribution to a data subset including maximal gaps only, then the resulting shape parameter was very close to zero, which is typical for random variables with an unbounded light-tailed distribution (the Gumbel type).

3.6 Is there a limiting distribution?

Our observations are compatible with the existence of a Gumbel limit law for (appropriately rescaled) maximal gaps, as well as for first-occurrence gaps between primes in progressions (P). However, the convergence to the hypothetical Gumbel limit law appears to be better for data sets comprising maximal gaps only, as opposed to data sets including all first-occurrence gaps (in a given range of primes in progressions (P) for a given q).

An alternative hypothesis is that the Gumbel limiting distribution exists for rescaled maximal gaps, but not for first-occurrence gaps. Of course it is also possible that there is no limiting distribution at all, and the Gumbel distribution is simply a good approximation of the rescaled gap values.

4 When do we expect the first occurrence of gap d?

Let d be the size of a gap between primes in progression (P): r + nq, and denote by

P_{f}(d; q, r) and P′_{f}(d; q, r)

the primes that, respectively, start and end the first occurrence of gap d. So we have

d = P′_{f}(d; q, r) − P_{f}(d; q, r).

Conjecture 5. Generalization of Polignac’s conjecture for an arithmetic progression (P): r, r + q, r + 2q, …. For every pair of coprime integers (q, r) and every d = n · lcm(2, q), n ∈ ℕ, we have

P_{f}(d; q, r) < ∞.

Moreover, every gap of size n · lcm(2, q), n ∈ ℕ, occurs infinitely often between primes in progression (P).

Conjecture 6. Let d be a gap between primes in (P). There exists a constant C such that for the sequence of first-occurrence gaps d infinitely often we have

e^{\sqrt{d/φ(q)}} < P_{f}(d; q, r) < C\sqrt{d} e^{\sqrt{d/φ(q)}},  (18)

and the difference P_{f}(d; q, r) − C\sqrt{d} e^{\sqrt{d/φ(q)}} changes its sign infinitely often as d → ∞.

For maximal gaps between primes in (P), we state the following stronger conjectures.

Conjecture 7. Let d = G_{q,r}(p′) be a maximal gap between primes in (P). Then there exists a constant C such that a positive proportion of maximal gaps satisfy the double inequality (18), and the difference P_{f}(d; q, r) − C\sqrt{d} e^{\sqrt{d/φ(q)}} changes its sign infinitely often as d → ∞.

Conjecture 8. Let d = G_{q,r}(p′) be a maximal gap between primes in (P). Then, as d → ∞, a positive proportion of maximal gaps satisfy

P_{f}(d; q, r) ≍ \sqrt{d} e^{\sqrt{d/φ(q)}}.  (19)

In other words, there are constants C_{0}, C_{1} > 0 such that a positive proportion of maximal gaps satisfy the double inequality

C_{0}\sqrt{d} e^{\sqrt{d/φ(q)}} < P_{f}(d; q, r) < C_{1}\sqrt{d} e^{\sqrt{d/φ(q)}}.  (20)

For primes up to 10^{14} and q ≤ 10^{5}, computations suggest that if we take C_{0} = \frac{1}{10}, C_{1} = 10, then the majority of maximal gap sizes will satisfy (20); a sizable proportion of non-maximal first-occurrence gaps will also be found within the bounds (20).

How did we arrive at the estimates (18)–(20)? The left-hand side e^{\sqrt{d/φ(q)}} in (18) stems from the conjecture [19, eq. (34)] that almost all maximal gaps between primes in (P) satisfy

G_{q,r}(p) < φ(q) log^{2} p.

(This is our generalization of Cramér’s conjecture [6].)

To see why we have C\sqrt{d} e^{\sqrt{d/φ(q)}} in the right-hand side of (18)–(20), consider the function

P̃(d, q) = \sqrt{d} e^{\sqrt{d/φ(q)}}.  (21)

For any fixed q ≥ 2, one can check that

lim_{x→∞} \frac{P̃(T_{0}(q, x), q)}{x} = e^{−1/2} ≈ 0.60653.  (22)

That is, for large d and x, the function e^{1/2}P̃(d, q) is “almost inverse” of T_{0}(q, x) in (6).

Remark 9. We do not know whether the lower bound in (18) is reversed infinitely often or finitely often. For the special case q = 2 (gaps in the sequence of all primes), heuristic models [2, 12] lead to lim sup_{x→∞} \frac{G(x)}{log^{2} x} ≥ 2e^{−γ} ≈ 1.1229—suggesting that, for first-occurrence prime

gaps, the lower bound in (18) is reversed infinitely often. However, it is quite difficult to find examples of progressions (P): r + nq with exceptionally early first occurrences of gaps d such that P′_{f}(d; q, r) < e^{\sqrt{d/φ(q)}} and the Cramér–Shanks–Granville ratio CSG = \frac{d_{q,r}(x)}{φ(q) log^{2} x} > 1. We know only a modest number of maximal gaps of this kind [19, Table 1], [30]–[32]. We have never seen examples of sign reversal of the lower bound in (18) (CSG > 1) for non-maximal first-occurrence gaps in (P). Note also that Sun [38, conj. 2.3] proposed a hypothesis similar to Firoozbakht’s conjecture for gaps between primes in (P), which would imply (at most) a finite number of such sign reversals for any given progression (P).

5 A detour: generalization of Brun’s constants

We will now give another (less direct) heuristic way of deriving the estimate C\sqrt{d} e^{\sqrt{d/φ(q)}} in (18)–(20). Our approach is to estimate the sum of reciprocals of prime pairs (p, p + d) separated by a given fixed gap d. (Wolf [40] used this heuristic approach to treat the case q = 2, obtaining the estimate^{2} \sqrt{d} e^{\sqrt{d}} for the first occurrence of gap d.)

First, let us recall some definitions. Twin primes are pairs of prime numbers (p, p + 2) separated by gap 2—the smallest possible gap between odd primes. Cousin primes are pairs of prime numbers (p, p + 4) separated by gap 4.

2The preprint [40] employs the “physical” notation where the relation f ∼ g is a shorthand for “the functions f and g have the same order of magnitude.” Thus \sqrt{d} e^{\sqrt{d}} is just an order-of-magnitude estimate.

Brun [5] proved in 1919 that the series consisting of reciprocal twin primes converges. Brun’s constant B_{2} for twin primes is the sum of reciprocals [9, 21, 23, 34, \underline{A065421}]

B_{2} = (\frac{1}{3} + \frac{1}{5}) + (\frac{1}{5} + \frac{1}{7}) + (\frac{1}{11} + \frac{1}{13}) + ⋯ ≈ 1.90216.

A generalization of Brun’s theorem exists for series of reciprocal values of prime pairs (p, p+d) separated by any fixed gap d [35]. For example, Brun’s constant B_{4} for cousin primes (with the pair (3, 7) omitted) is [39, \underline{A194098}]

B_{4} = (\frac{1}{7} + \frac{1}{11}) + (\frac{1}{13} + \frac{1}{17}) + (\frac{1}{19} + \frac{1}{23}) + ⋯ ≈ 1.19704.

Note that twin primes p, p + 2 are always consecutive. Except for the pair (3, 7), primes p, p + 4 are also necessarily consecutive. If d ≥ 6, however, there may also be other primes between the primes p and p + d. In what follows, we will consider gaps d ≥ 6.

Suppose that primes p and p′ are in the residue class r (mod q), p < p′, and there are no other primes in this residue class between p and p′. If d = n · lcm(2, q), then the number of gaps of size d = p′ − p between primes p, p′ ≡ r (mod q), with p′ ≤ x, is roughly

τ_{q,r}(d, x) ≈ C_{2} ∏_{{p|d \atop p>2}} \frac{p − 1}{p − 2} · \frac{π^{2}(x)}{φ^{2}(q)x} e^{− \frac{d·π(x)}{φ(q)x}} ,  (23)

cf. [11, eq. (2)] and [19, eq. (30)]. In formula (23), p runs through odd prime factors of d,

C_{2} = \frac{c}{s},  c = lcm(2, q),  s = mean_{{d = nc \atop n∈ℕ}} ∏_{{p|d \atop p>2}} \frac{p − 1}{p − 2} = Π_{2}^{−1} ∏_{{p|q \atop p>2}} \frac{p}{p − 1},  (24)

and Π_{2} = ∏_{p>2} \frac{p(p−2)}{(p−1)^{2}} ≈ 0.66016 is the twin prime constant. In particular, s = Π_{2}^{−1} ≈ 1.51478

if q is a power of 2; see Appendix. Note that

τ_{q,r}(d, x) = 0 if 2 ∤ d or q ∤ d.  (25)

Let T_{d;q,r} denote the set of primes p, p′ at both ends of the gaps d counted in (23):

T_{d;q,r} = {p, p′ : p′ − p = d and p, p′ ≡ r mod q}.  (26)

Consider the sum of reciprocals of all primes in T_{d;q,r}:

B_{d}(q, r) = ∑_{p ∈T_{d;q,r}} \frac{1}{p}.  (27)

We adopt the rule that if a given gap d appears twice in a row: d = p′ − p = p′′ − p′, then the corresponding middle prime p′ is counted twice. The real numbers B_{d}(q, r) defined by (27) can be called the generalized Brun constants for residue class r (mod q).

Let us define the partial (finite) sums:

B_{d}(x; q, r) = ∑_{{p∈T_{d;q,r} \atop p≤x}} \frac{1}{p}.  (28)

Hereafter we will work with rough estimates of partial sums (28). To distinguish the actual partial sum B_{d}(x; q, r) from its estimated value, we will write B_{d}(x; q) for the estimate. Likewise, for a rough estimate of the constant (27), we will write B_{d}(∞; q). Our estimates B_{d}( ·; q) will be independent of r.

Given a gap size d = p′ − p, observe that the density of pairs (p, p′) ⊂ T_{d;q,r} near x is roughly τ_{q,r}(d, x)/x. Putting π(x) ≈ x/ log(x) in equation (23), we obtain

B_{d}(x; q) ≈ ∑_{p∈T_{d;q,r}} \frac{1}{p} − ∑_{{p∈T_{d;q,r} \atop p>x}} \frac{1}{p} ≈ B_{d}(∞, q) − 2C_{2} ∏_{p|d} \frac{p − 1}{p − 2} ∫_{x}^{∞}\frac{e^{− \frac{d}{φ(q) log u}}}{φ^{2}(q) u log^{2} u} du. (29)

After the substitution v = \frac{d}{φ(q) log u} the integral (29) can be calculated explicitly:

B_{d}(x; q) ≈ B_{d}(∞; q) − \frac{2C_{2}}{φ(q)d} ∏_{p|d} \frac{p − 1}{p − 2} (1 − e^{− \frac{d}{φ(q) log x}} ) .  (30)

We will require that B_{d}(x; q) → 0 as x → 1^{+} (indeed, the actual partial sum B_{d}(x; q, r) will be zero up to the first occurrence of the gap d). Taking the limit x → 1^{+} in (30) we obtain

B_{d}(∞; q) ≈ \frac{2C_{2}}{φ(q)d} ∏_{p|d} \frac{p − 1}{p − 2}.  (31)

Then the estimate B_{d}(x; q), as a function of x for fixed q and d, has the form

B_{d}(x; q) ≈ \frac{2C_{2}}{φ(q)d} ∏_{p|d} \frac{p − 1}{p − 2} e^{− \frac{d}{φ(q) log x}} .  (32)

Recall that, for d = n · lcm(2, q), the mean value of ∏_{p|d} \frac{p−1}{p−2} is s; see (23), (24). Therefore, we can skip the ratio ∏_{p|d} \frac{p−1}{p−2}/s (which is near 1 infinitely often) and get

B_{d}(x; q) ≈ \frac{2c}{φ(q)d} e^{− \frac{d}{φ(q) log x}} = \frac{A}{d} e^{− \frac{d}{φ(q) log x}} ,  (33)

where c = lcm(2, q) and A = 2c/φ(q) = O(log log q); moreover^{3} A = O(1) for prime q.

3We easily check that A = 4 when q = 2, and A ≤ 6 when q is an odd prime. On the other hand, one can also show that A = O(log log q) when q is a primorial (which constitutes an extreme case; see [26]).

Suppose that gap d occurs for the first time at ξ = P_{f}(d; q, r). We can estimate ξ from the condition B_{d}(ξ; q) ≈ 2/ξ, so we have the following equation for ξ:

\frac{A}{d} e^{− \frac{d}{φ(q) log ξ}} = \frac{2}{ξ}.  (34)

Taking the log of both sides of (34) and discarding the small term log \frac{A}{2}, we get a quadratic equation for t = log ξ:

t^{2} − t log d − d/φ(q) = 0.  (35)

Its positive solution is t ≈ \frac{1}{2} log d + \sqrt{d/φ(q)}, which allows us to conjecture that

ξ = P_{f}(d; q, r) ≍ \sqrt{d} e^{\sqrt{d/φ(q)}}  (36)

infinitely often.

Remark 10. Setting q = 2 in (36), for the first occurrence of gap d in the sequence of all primes we get p_{f}(d) ≍ \sqrt{d} e^{\sqrt{d}}; cf. [40]. Thus, in progressions (P) with large q, gaps of a given size d appear much earlier (due to the division by φ(q) under square root in the exponent). Note, however, that the “natural unit” of gaps in progressions (P) is larger than that for all primes; namely, all even gaps between primes in (P) have sizes n · lcm(2, q), n ∈ ℕ.

6 How many first-occurrence gaps are there below x?

Using a modified version of our PARI/GP code from [19] we computed the mean numbers of first-occurrence gaps between primes p = r + nq in intervals [x, ex], x = e^{j}, j = 1, 2, …, 27. Figure 3 shows the results of this computational experiment for q = 17011. For comparison, we also computed the corresponding mean numbers of record (maximal) gaps between primes p = r+nq in the same set of intervals [x, ex]; the results are shown in Fig. 4. The computation resulting in Figs. 3, 4 took about 30 hours on an Intel Core i7-8550U CPU.

We found that, for large enough x, the mean number of first-occurrence gaps between primes r + nq ∈ [x, ex] grows like a linear function of log x; see Fig. 3. It is reasonable to expect that the total number N′_{q,r}(x) of first-occurrence gaps between primes ≤ x in progression (P): r + nq can be approximated by a quadratic function of log x, and for large x we will have

N′_{q,r}(x) ≈ \frac{T_{0}(q, x)}{lcm(2, q)} ≲ \frac{φ(q) log^{2} x}{lcm(2, q)} = O(log^{2} x),  (37)

where T_{0}(q, x) is given by (6).

Figure 3: Mean number of first-occurrence gaps between primes p = r + nq ∈ [x, ex], for q = 17011, x = e^{j}, j ≤ 27. Averaging for all r ∈ [1, 17010].

Figure 4: Mean number of record (maximal) gaps between primes p = r + nq ∈ [x, ex], for q = 17011, x = e^{j}, j ≤ 27. Averaging for all r ∈ [1, 17010].

Thus the number N′_{q,r}(x) of first-occurrence gaps between primes in (P) is asymptotically much greater than the number N_{q,r}(x) of record (maximal) gaps in (P). Indeed, the latter seems to be only O(log x). More precisely, our computations (see Fig. 4) suggest that the average number of maximal gaps observed in [x, ex] is

mean_{r} (N_{q,r}(ex) − N_{q,r}(x)) ≈ 2 − \frac{κ(q)}{log x + δ(q)}.  (38)

Accordingly, we conjecture that the number of maximal gaps between primes ≤ x in (P) is

N_{q,r}(x) ∼ 2 log x = O(log x)  as x → ∞.  (39)

The constant 2 in (38) and (39) can be justified by a heuristic argument based on two hypotheses: the generalized Shanks conjecture (4) and the assumption that, on average, consecutive record gaps near x differ by the average gap ∼ φ(q) log x between primes in (P). (See [18, 19] for details.)

7 Maximal gaps and first occurrences as functions of their sequential number

As before, consider the arithmetic progression (P): r, r + q, r + 2q, r + 3q, ….

Conjecture 11. Let S(n; q, r) be the size of the n-th first-occurrence gap between primes in progression (P). Then the sizes S(n; q, r) of almost all first-occurrence gaps satisfy

n ≤ S(n; q, r) ≤ 2nq⌈log^{2} q⌉.  (40)

Moreover, all gap sizes divisible by lcm(2, q) occur early enough, so that

S(n; q, r) ≈ n · lcm(2, q) = O_{q}(n)  as n → ∞.  (41)

Example: for q = 6 and r = 5, we have S(n; 6, 5) = \underline{A334543}(n).

For comparison, here is a similar conjecture for maximal gap sizes:

Conjecture 12. Let R(n; q, r) be the size of the n-th record (maximal) gap between primes in (P). Then the sizes R(n; q, r) of almost all maximal gaps satisfy [18, 33]

\frac{φ(q)n^{2}}{6} < R(n; q, r) < φ(q)n^{2} + (n + 2)q log^{2} q.  (42)

We do not know any exceptions to (42); in particular, there are no exceptions for q ≤ 2000, n < 15. Heuristic reasoning [18, 19] suggests that for large n we will have

R(n; q, r) ≈ \frac{φ(q)n^{2}}{4} = O_{q}(n^{2})  as n → ∞.  (43)

(At the same time, for small n, the ratio \frac{R(n;q,r)}{φ(q)n^{2}} may be greater than 1.)

Example: for q = 6 and r = 5, we have R(n; 6, 5) = \underline{A268928}(n).

Conjectures 11 and 12 are another way to restate our observation that first-occurrence gaps between primes in progression (P) are much more numerous than maximal gaps. Remark 13. Setting n = 0 in (42), we get that the “0th record gap” is less than 2q log^{2} q, which can be interpreted as an almost-sure upper bound on the least prime in progression (P); cf. [20, sect.2]. That is, the “0th record gap” between primes in (P) is the distance from 0 to the least prime in (P), which is (almost always) bounded by 2q log^{2} q.

8 Appendix

In this appendix we calculate the average value of the product

S(d) = ∏_{{p|d \atop p>2}} \frac{p − 1}{p − 2}  (44)

when d runs through a given arithmetic progression, d = r + nq, n ∈ ℕ. So our goal is to find

mean_{{d=r+nq \atop n∈ℕ}} S(d) = lim_{N→∞} \frac{1}{N} ∑_{n=1}^{N} S(r + nq).

For generality, in the appendix, q and r are not necessarily coprime, and r is nonnegative. In particular, we will derive the expression for s in (24) for the case d = nq (r = 0).

Bombieri and Davenport [3] proved that

mean_{d∈ℕ} S(d) = mean_{d∈ℕ} ∏_{{p|d \atop p>2}} \frac{p − 1}{p − 2} = Π_{2}^{−1} = 1.51478 …,

where Π_{2} is the twin prime constant \underline{A005597}:

Π_{2} = ∏_{p>2} \frac{p(p − 2)}{(p − 1)^{2}} = 0.66016 ….

If, instead of averaging S(d) over all natural numbers, we restrict the averaging process to an arithmetic progression r+nq, then the resulting average might become larger or smaller than Π_{2}^{−1}—or it might remain unchanged (= Π_{2}^{−1}). A few special cases are possible, depending on the values of q and r.

8.1 Base cases: prime q

(i) If q = 2, we have S(2n) = S(n) for all n ∈ ℕ. Therefore, for even d,

mean_{d=2n} S(d) = mean_{d∈ℕ} S(d) = Π_{2}^{−1}.

But this immediately implies that, for odd d, we must also have

mean_{d=2n+1} S(d) = mean_{d∈ℕ} S(d) = Π_{2}^{−1}.

(ii) Suppose q = p′ is an odd prime and gcd(p′, r) = 1. Let

ξ = ξ(p′) = mean_{d=np′} S(d)
η = η(p′) = mean_{d=r+np′} S(d).

Observe that every term in progression d = np′ has the prime factor p′; so the factor \frac{p′−1}{p′−2} is always present in the corresponding product (44). On the other hand, terms in progression d = r + np′ never have the prime factor p′; so the factor \frac{p′−1}{p′−2} is never present in the corresponding product (44). All other odd prime factors p (resp., \frac{p−1}{p−2}), p ≠ p′, are sometimes present in both progressions (resp., products), with probability 1/p. Therefore, we require that

ξ = η · \frac{p′ − 1}{p′ − 2}.  (45)

The factor \frac{p′−1}{p′−2} in (45) is the same as in the definition of S(d).

Note that there are p′ − 1 residue classes mod p′ for which the mean values of S(d) are η, and only one “special” residue class (0 mod p′) for which the mean value of S(d) is ξ. But the arithmetic average of all these p′ mean values is equal to mean_{d∈ℕ} S(d), which is Π_{2}^{−1}:

\frac{1}{p′} · ξ + \frac{p′ − 1}{p′} · η = Π_{2}^{−1}.  (46)

Solving equations (45) and (46) together, we find

ξ = mean_{d=np′} S(d) = \frac{p′}{p′ − 1} · Π_{2}^{−1},  (47)
η = mean_{d=r+np′}S(d) = \frac{p′(p′ − 2)}{(p′ − 1)^{2}} · Π_{2}^{−1}.  (48)

Example: for q = 3, we have

mean_{d=3n} S(d) = \frac{3}{2}Π_{2}^{−1},  mean_{d=3n+1} S(d) = mean_{d=3n+2} S(d) = \frac{3}{4}Π_{2}^{−1}.

Formulas (47) and (48) encode the following

Factors Principle. For progressions d = np′ where each term is guaranteed to have a factor p′, the average product S(d) equals Π_{2}^{−1} multiplied by \frac{p′}{p′−1} > 1. For progressions d = r + np′ where each term never has the factor p′, the average is Π_{2}^{−1} multiplied by \frac{p′(p′−2)}{(p′−1)^{2}} < 1.

8.2 Remaining cases: composite q

The above argument considered progressions with one “special” prime factor p′. A straightforward modification of the argument allows us to extend the consideration from progressions with k “special” factors to those with k + 1 “special” factors. Therefore, we can apply the “factors principle” to composite values of q.

(A) Let q be a power of 2. (This case is similar to (i) in sect. 8.1.) In this case, for every odd prime p, terms of our arithmetic progression r + nq span all residue classes modulo p. So here the average value of S(d) remains unchanged:

mean_{d=r+qn} S(d) = Π_{2}^{−1}.

Example: for q = 4, we have mean_{d=4n} S(d) = mean_{d=4n+1} S(d) = mean_{d=4n+2} S(d) = mean_{d=4n+3} S(d) = Π_{2}^{−1}.

(B) Suppose q ≠ 2^{m} is composite and gcd(q, r) = 1. Here all terms of our arithmetic progression r+nq are not divisible by prime factors of q, while divisibility by all other primes is neither ensured nor precluded. We have

mean_{d=r+nq} S(d) = Π_{2}^{−1} · ∏_{{p|q \atop p>2}} \frac{p(p − 2)}{(p − 1)^{2}}.

Example: for q = 15 and r = 1, we have mean_{d=15n+1} S(d) = \frac{3}{4} · \frac{15}{16} · Π_{2}^{−1} = \frac{45}{64}Π_{2}^{−1}.

(C) Suppose q ≠ 2^{m} is composite and r = 0. All terms nq in our arithmetic progression are divisible by prime factors of q, while divisibility by all other primes is neither ensured nor precluded. We have

mean_{d=nq} S(d) = Π_{2}^{−1} · ∏_{{p|q \atop p>2}} \frac{p}{p − 1}.

Example: for q = 15 and r = 0, we have mean_{d=15n} S(d) = \frac{3}{2} · \frac{5}{4} · Π_{2}^{−1} = \frac{15}{8}Π_{2}^{−1}.

(D) Suppose q ≠ 2^{m} is composite, r ≠ 0, gcd(q, r) > 1. (This case is, in a sense, a combination of the above cases.) Terms of our arithmetic progression r + nq are divisible by common prime factors of q and r, but not by other prime factors of q; divisibility by all other primes is neither ensured nor precluded. We have

mean_{d=r+nq} S(d) = Π_{2}^{−1} · ∏_{{P |q, P |r \atop P >2}} \frac{P}{P − 1} · ∏_{{p|q, p ∤ r \atop p>2}} \frac{p(p − 2)}{(p − 1)^{2}}.  (49)

Example: for q = 30 and r = 3, we have mean_{d=30n+3} S(d) = \frac{3}{2} · \frac{15}{16} · Π_{2}^{−1} = \frac{45}{32}Π_{2}^{−1}.

Remark 14. Formula (49) is in fact applicable to an arbitrary pair (q, r); it subsumes all preceding cases. Formulas like this can be derived not only in our setup related to the twin prime constant Π_{2} but also for similar average products related to the Hardy–Littlewood k-tuple constants, as well as for other average products, e.g., mean_{{d=r+nq \atop n∈ℕ}} ∏_{{p|d \atop p>m}} \frac{p+a}{p+b}.

9 Acknowledgments

We are grateful to the anonymous referee and to all contributors and editors of the websites

MersenneForum.org, OEIS.org, and PrimePuzzles.net. Special thanks to Martin Raab,

whose extensive computations provided new examples of exceptionally large gaps between primes in residue classes [30]–[32]. We gratefully acknowledge the valuable input and encouragement of the late Prof. Thomas R. Nicely, whose emails we retain to this day.

References

[1] R. C. Baker, G. Harman, and J. Pintz, The difference between consecutive primes, II. Proc. Lond. Math. Soc. 83 (2001), 532–562.

[2] W. Banks, K. Ford, and T. Tao, Large prime gaps and probabilistic models, preprint,

2019. Available at http://arxiv.org/abs/1908.08613.

[3] E. Bombieri and H. Davenport, Small differences between prime numbers. Proc. Royal Soc. A293 (1966), 1–18.

[4] R. P. Brent, The first occurrence of large gaps between successive primes. Math. Comp. 27 (1973), 959–963.

[5] V. Brun, La série 1/5 + 1/7 + ⋯ où les dénominateurs sont nombres premiers jumeaux est convergente ou finie. Bull. Sci. Math. 43 (1919), 100–104.

[6] H. Cramér, On the order of magnitude of difference between consecutive prime numbers. Acta Arith. 2 (1937), 23–46.

[7] P. G. L. Dirichlet, Beweis des Satzes, dass jede unbegrenzte arithmetische Progression, deren erstes Glied und Differenz ganze Zahlen ohne gemeinschaftlichen Factor sind, unendlich viele Primzahlen enthält. Abhandlungen der Königlichen Preußischen Akademie der Wissenschaften zu Berlin, 48 (1837), 45–71.

[8] K. Ford, B. Green, S. Konyagin, J. Maynard, and T. Tao, Long gaps between primes. J. Amer. Math. Soc. 31 (2018), 65–105. Available at http://arxiv.org/abs/1412.5029.

[9] P. Fry, J. Nesheiwat, and B. Szymanski, Computing twin primes and Brun’s constant: a distributed approach. In: Proceedings. The Seventh International Symposium on High Performance Distributed Computing IEEE Comput. Soc., 1998, pp. 42–49.

[10] S. Funkhouser, D. A. Goldston, and A. H. Ledoan, Distribution of large gaps between primes. In J. Pintz and M. Th. Rassias, eds., Irregularities in the Distribution of Prime Numbers: From the Era of Helmut Maier’s Matrix Method and Beyond, Springer, 2018,

pp. 45–67. Available at http://arxiv.org/abs/1802.07609.

[11] D. A. Goldston and A. H. Ledoan, On the differences between consecutive prime numbers, I. In Combinatorial Number Theory. Proceedings of the Integers Conference 2011,

pp. 37–44. Available at http://arxiv.org/abs/1111.3380.

[12] A. Granville, Harald Cramér and the distribution of prime numbers. Scand. Actuar. J. 1 (1995), 12–28.

[13] E. J. Gumbel, Statistics of Extremes. Columbia University Press, 1958.

[14] J.-M. de Koninck and F. Luca, Analytic Number Theory: Exploring the Anatomy of Integers. Graduate Studies in Mathematics, 134, AMS, 2012.

[15] A. Kourbatov, Maximal gaps between prime k-tuples: a statistical approach. J. Integer Sequences 16 (2013), Article 13.5.2.

[16] A. Kourbatov, The distribution of maximal prime gaps in Cramér’s probabilistic model of primes. Int. J. Stat. Probab. 3 (2014), 18–29. Available at http://arxiv.org/abs/

1401.6959.

[17] A. Kourbatov, On the distribution of maximal gaps between primes in residue classes,

preprint, 2016. Available at http://arxiv.org/abs/1610.03340.

[18] A. Kourbatov, On the nth record gap between primes in an arithmetic progression. Int. Math. Forum, 13 (2018), 65–78. Available at http://arxiv.org/abs/1709.05508.

[19] A. Kourbatov and M. Wolf, Predicting maximal gaps in sets of primes. Mathematics,

7 (2019), 400. Available at http://arxiv.org/abs/1901.03785.

[20] J. Li, K. Pratt, and G. Shakan, A lower bound for the least prime in an arithmetic progression. Quart. J. Math. 68 (2017), 729–758. Available at http://arxiv.org/

abs/1607.02543.

[21] T. R. Nicely, Enumeration to 1.6 × 10^{15} of the twin primes and Brun’s constant, 1999.

Available at https://faculty.lynchburg.edu/~nicely/twins/twins2.html.

[22] T. R. Nicely, New maximal prime gaps and first occurrences. Math. Comp. 68 (1999), 1311–1315.

[23] T. R. Nicely, A new error analysis for Brun’s constant. Virginia J. Sci. 52 (2001),

45–55. Available at https://faculty.lynchburg.edu/~nicely/twins/twins4.html.

[24] T. R. Nicely, First occurrence prime gaps, preprint, 2018. Available at

https://faculty.lynchburg.edu/~nicely/gaps/gaplist.html.

[25] T. R. Nicely and B. Nyman, New prime gaps between 10^{15} and 5 × 10^{16}. J. Integer Sequences 6 (2003), Article 03.3.1.

[26] J.-L. Nicolas, Petites valeurs de la fonction d’Euler. J. Number Theory, 17 (1983), 375–388.

[27] T. Oliveira e Silva, S. Herzog, and S. Pardi, Empirical verification of the even Goldbach conjecture and computation of prime gaps up to 4 × 10^{18}. Math. Comp. 83 (2014), 2033–2060.

[28] The PARI Group. PARI/GP version 2.11.2, 64-bit, Univ. Bordeaux, 2019. Available at

http://pari.math.u-bordeaux.fr/.

[29] A. de Polignac, Recherches nouvelles sur les nombres premiers. Comptes Rendus, 29 (1849), 397–401.

[30] M. Raab, Prime gaps in residue classes where CSG > 1 is possible, MersenneForum.org,

2020. Available at https://www.mersenneforum.org/showthread.php?t=25015.

[31] M. Raab, Exceptional gap g = 45480858 (CSG > 1) between primes p ≡ r (mod q) with prime q and r: q = 128477, r = 83341, p = 37855579, private communication, March 2020.

[32] M. Raab, Exceptional gap g = 54264 > max(q^{2}, φ(q) log^{2} p) between primes p ≡ r (mod q): q = 152, r = 33, p = 825353008489, private communication, May 2020.

[33] C. Rivera (ed.), Conjecture 84. Conjecture related to primes in AP, PrimePuzzles.net,

2019. Available at http://www.primepuzzles.net/conjectures/conj_084.htm.

[34] P. Sebah and X. Gourdon, Introduction to twin primes and Brun’s constant computa-

tion, preprint, 2002. Available at http://numbers.computation.free.fr/Constants/
Primes/twin.pdf.

[35] B. Segal, Generalisation du théorème de Brun. Dokl. Akad. Nauk SSSR, 1930 (1930), 501–507.

[36] D. Shanks, On maximal gaps between successive primes. Math. Comp. 18 (1964), 646–651.

[37] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2020. Published

electronically at https://oeis.org/.

[38] Z.-W. Sun, Conjectures involving arithmetical sequences. In S. Kanemitsu, H. Li, and J. Liu, eds., Number Theory: Arithmetic in Shangri-La, Proceedings of the 6th China-Japan Seminar, World Scientific, 2013, pp. 244–258. Available at http://arxiv.org/

abs/1208.2683.

[39] M. Wolf, On the twin and cousin primes, Preprint IFTUWr 909/96, 1996.

[40] M. Wolf, First occurrence of a given gap between consecutive primes, Preprint IFTUWr 911/97, 1997.

[41] M. Wolf, Some heuristics on the gaps between consecutive primes, preprint, 2011.

    Available at http://www.arxiv.org/abs/1102.0481.

[42] M. Wolf, Nearest-neighbor-spacing distribution of prime numbers and quantum chaos. Phys. Rev. E, 89 (2014), 022922–1. Available at http://arxiv.org/abs/1212.3841.

[43] J. Young and A. Potler, First occurrence prime gaps, Math. Comp. 52 (1989), 221–224.

2010 Mathematics Subject Classification: Primary 11N05; secondary 11N56, 11N64. Keywords: arithmetic progression, Brun constant, Cramér conjecture, Gumbel distribution, prime gap, residue class, Shanks conjecture.

(Concerned with sequences \underline{A000010}, \underline{A001620}, \underline{A005597}, \underline{A014320}, \underline{A065421}, \underline{A167864}, \underline{A194098}, \underline{A268925}, \underline{A268928}, \underline{A330853}, \underline{A330854}, \underline{A330855}, \underline{A334543}, \underline{A334544}, \underline{A334545}, \underline{A335366}, and \underline{A335367}.)

Received June 11 2020; revised version received September 15 2020, September 19 2020. Published in Journal of Integer Sequences, October 15 2020.

Return to Journal of Integer Sequences home page.