Two algorithms to find primes in patterns

By Jonathan P. Sorenson and Jonathan Webster

Abstract

Let k greater-than-or-equal-to 1 be an integer, and let upper P equals left-parenthesis f 1 left-parenthesis x right-parenthesis , …, f Subscript k Baseline left-parenthesis x right-parenthesis right-parenthesis be k admissible linear polynomials over the integers, or the pattern. We present two algorithms that find all integers x where max left-brace f Subscript i Baseline left-parenthesis x right-parenthesis right-brace less-than-or-equal-to n and all the f Subscript i Baseline left-parenthesis x right-parenthesis are prime.

Our first algorithm takes upper O Subscript upper P Baseline left-parenthesis n slash left-parenthesis log log n right-parenthesis Superscript k Baseline right-parenthesis arithmetic operations using upper O left-parenthesis k StartRoot n EndRoot right-parenthesis space.

Our second algorithm takes slightly more time, upper O Subscript upper P Baseline left-parenthesis n slash left-parenthesis log log n right-parenthesis Superscript k minus 1 Baseline right-parenthesis arithmetic operations, but uses only n Superscript 1 slash c space for c greater-than 2 a fixed constant. The correctness of this algorithm is unconditional, but our analysis of its running time depends on two reasonable but unproven conjectures.

We are unaware of any previous complexity results for this problem beyond the use of a prime sieve.

We also implemented several parallel versions of our second algorithm to show it is viable in practice. In particular, we found some new Cunningham chains of length 15, and we found all quadruplet primes up to 10 Superscript 17 .

1. Introduction

Mathematicians have long been interested in prime numbers and how they appear in patterns. (See, for example, Reference 12, Ch. A.) In this paper, we are interested in the complexity of the following algorithmic problem:

Given a pattern and a bound n , find all primes less-than-or-equal-to n that fit the pattern.

To address this, first we will discuss and define a pattern of primes, then we will look at what is known about the distribution of primes in patterns to see what we can reasonably expect for the complexity of this problem, and finally we will discuss previous work and state our new results.

1.1. Prime patterns

Perhaps the simplest of patterns of primes are the twin primes, which satisfy the pattern left-parenthesis x comma x plus 2 right-parenthesis where both x and x plus 2 are prime. Examples include 59, 61 and 101, 103.

We can, of course, generalize this to larger patterns. For example, prime quadruplets have the form left-parenthesis x , x plus 2 , x plus 6 , x plus 8 right-parenthesis , and examples include 11, 13, 17, 19 and 1481, 1483, 1487, 1489.

Larger patterns of primes of this type are called prime k -tuples. If the k -tuple has the smallest possible difference between its first and last primes (its diameter), it is also called a prime constellation. The pattern left-parenthesis x , x plus 2 , x plus 6 , x plus 8 right-parenthesis is a constellation, as 8 is the smallest possible diameter for a pattern of length 4. There are two constellations of length 3: left-parenthesis x , x plus 2 , x plus 6 right-parenthesis and left-parenthesis x , x plus 4 , x plus 6 right-parenthesis . See, for example, Reference 7, §1.2.2 or Reference 25, Ch. 3.

Sophie Germain studied the pattern left-parenthesis x comma 2 x plus 1 right-parenthesis , which was later generalized to Cunningham chains of two kinds. Chains of the first kind have the pattern left-parenthesis x , 2 x plus 1 , 4 x plus 3 , 8 x plus 7 , ellipsis right-parenthesis , and chains of the second kind have the pattern left-parenthesis x , 2 x minus 1 , 4 x minus 3 , 8 x minus 7 , ellipsis right-parenthesis .

Chernick Reference 6 showed that any prime pattern of the form left-parenthesis 6 x plus 1 , 12 x plus 1 , 18 x plus 1 right-parenthesis gives a Carmichael number composed of the product of these three primes.

Let k greater-than 0 be an integer. A prime pattern of size k is a list of k linear polynomials over the integers with positive leading coefficients, left-parenthesis f 1 left-parenthesis x right-parenthesis comma ellipsis comma f Subscript k Baseline left-parenthesis x right-parenthesis right-parenthesis . A pattern of size k is admissible if for every prime p less-than-or-equal-to k , there is an integer x such that p does not divide any of the f Subscript i Baseline left-parenthesis x right-parenthesis . For an algorithm to test for pattern admissibility, see Reference 25, pp. 62–63.

We restrict our notion of pattern to linear polynomials in this paper.

1.2. The distribution of primes in patterns

The unproven twin prime conjecture states there are infinitely many twin primes. Yitang Zhang Reference 33 recently showed that there is a positive integer h such that the pattern left-parenthesis x comma x plus h right-parenthesis is satisfied by infinitely many primes.

The Hardy-Littlewood k -tuple conjecture Reference 14 implies that each pattern, with leading coefficients of 1, that is admissible will be satisfied by primes infinitely often. Further, the conjecture implies that the number of primes less-than-or-equal-to n in such a pattern of length k is roughly proportional to n slash left-parenthesis log n right-parenthesis Superscript k .

For twin primes, then, the Hardy-Littlewood conjecture gives an estimate of

2 upper C 2 StartFraction n Over left-parenthesis log n right-parenthesis squared EndFraction

for the number of twin primes less-than-or-equal-to n , where upper C 2 almost-equals 0.6601 ellipsis is the twin primes constant. Brun’s theorem gives an upper O left-parenthesis n slash left-parenthesis log n right-parenthesis squared right-parenthesis upper bound for the number of twin primes less-than-or-equal-to n . For every k -tuple with k greater-than-or-equal-to 2 , there is a corresponding conjectured constant of proportionality that depends on the pattern and on k , generalizing the twin primes constant.

Dickson’s conjecture Reference 8 states that there are infinitely many primes satisfying any fixed admissible pattern, even with leading coefficients greater-than 1 . Thus, it applies to fixed-length Cunningham chains as well.

We have the following upper bound, due to Halberstam and Richert Reference 13, Thm. 2.4.

Lemma 1.

Given an admissible pattern left-parenthesis f 1 left-parenthesis x right-parenthesis comma ellipsis comma f Subscript k Baseline left-parenthesis x right-parenthesis right-parenthesis of length k , the number of integers x such that the f Subscript i Baseline left-parenthesis x right-parenthesis are all simultaneously prime and max left-brace f Subscript i Baseline left-parenthesis x right-parenthesis right-brace less-than-or-equal-to n is upper O left-parenthesis n slash left-parenthesis log n right-parenthesis Superscript k Baseline right-parenthesis .

Here the implied constant of the big- upper O can depend on k but does not depend on the coefficients of the f Subscript i .

1.3. Previous work

We can obtain a rather straightforward analysis by simply finding all primes less-than-or-equal-to n and then scanning to see how many tuples match the pattern. Note that it is not necessary to write all the primes down; we can scan them in small batches as we go. Since the scan phase is fast, the bottleneck would be finding the primes using a sieve. The Atkin-Bernstein sieve Reference 2 does this using at most upper O left-parenthesis n slash log log n right-parenthesis arithmetic operations and StartRoot n EndRoot space. Galway Reference 10 showed how to reduce space further to roughly n Superscript 1 slash 3 , but this version could not use the wheel data structure and requires upper O left-parenthesis n right-parenthesis arithmetic operations. See also Reference 16.

We follow the convention from the analysis of prime sieves of not charging for the space used by the output of the algorithm. Note that if we charged for the space of the output, we could not expect to do better than n slash left-parenthesis log n right-parenthesis Superscript k minus 1 bits in general.

A more specialized algorithm that searches for only the primes in the pattern and not all the primes should do much better. Günter Löh Reference 20 and Tony Forbes Reference 9 described algorithms to do exactly this but gave no runtime analysis. It seems likely their algorithms are faster than upper O left-parenthesis n slash log log n right-parenthesis , but without an analysis, we don’t know if this is true or not. Note that Forbes outlined an odometer-like data structure that seems to be similar to the wheel data structure we employ.

Of course, by the prime number theorem, there are only about n slash log n primes less-than-or-equal-to n , so the current best prime sieves use log n slash log log n arithmetic operations per prime on average. We do not know if anything smaller is possible. Applying this average cost to the results of Lemma 1, we can hope for an algorithm that takes upper O left-parenthesis n slash left-parenthesis log log n right-parenthesis Superscript k Baseline right-parenthesis arithmetic operations to find all primes less-than-or-equal-to n in a fixed pattern of length k .

In essence, this is what we prove as our main result.

1.4. New results

Our contribution is the following.

Theorem 1.

There is an algorithm that when given a list of k distinct linear polynomials over the integers, with positive leading coefficients, upper P equals left-parenthesis f 1 left-parenthesis x right-parenthesis comma ellipsis comma f Subscript k Baseline left-parenthesis x right-parenthesis right-parenthesis (the pattern), and a search bound n finds all integers x such that max left-brace f Subscript i Baseline left-parenthesis x right-parenthesis right-brace less-than-or-equal-to n and all the f Subscript i Baseline left-parenthesis x right-parenthesis are prime. This algorithm uses at most upper O Subscript upper P Baseline left-parenthesis n slash left-parenthesis log log n right-parenthesis Superscript k Baseline right-parenthesis arithmetic operations and upper O left-parenthesis k StartRoot n EndRoot right-parenthesis bits of space.

This algorithm extends the Atkin-Bernstein prime sieve with our space-saving wheel sieve. See Reference 28Reference 29Reference 30.

The StartRoot n EndRoot space needed by this algorithm limits its practicality. By replacing the Atkin-Bernstein sieve with the sieve of Eratosthenes combined with prime tests, we can greatly reduce the need for space.

Theorem 2.

Let c greater-than 2 . There is an algorithm that when given a list of k greater-than 2 distinct linear polynomials over the integers, with positive leading coefficients, upper P equals left-parenthesis f 1 left-parenthesis x right-parenthesis comma ellipsis comma f Subscript k Baseline left-parenthesis x right-parenthesis right-parenthesis (the pattern), and a search bound n finds all integers x such that max left-brace f Subscript i Baseline left-parenthesis x right-parenthesis right-brace less-than-or-equal-to n and all the f Subscript i Baseline left-parenthesis x right-parenthesis are prime. This algorithm uses at most upper O Subscript upper P Baseline left-parenthesis n slash left-parenthesis log log n right-parenthesis Superscript k minus 1 Baseline right-parenthesis arithmetic operations and n Superscript 1 slash c bits of space, under the assumption of Conjectures 1 and 2 (see below). Correctness of the output is unconditional.

If k greater-than 6 , then Conjecture 1 is not needed. We use the sieve of Eratosthenes with primes up to a bound upper B equals n Superscript 1 slash c , after which we apply a base-2 pseudoprime test and then a version of the AKS prime test Reference 1 that was improved to take left-parenthesis log n right-parenthesis Superscript 6 plus o left-parenthesis 1 right-parenthesis time Reference 19. Our goal here is to balance the cost of sieving with the cost of prime testing. For the range 2 less-than k less-than-or-equal-to 6 , to keep the cost of prime testing low enough, we replace the AKS prime test with the pseudosquares prime test of Lukes, Patterson, and Williams Reference 21. This prime test takes only upper O left-parenthesis left-parenthesis log n right-parenthesis squared right-parenthesis time under the condition of an unproven but reasonable conjecture on the distribution of pseudosquares due to Bach and Huelsbergen Reference 3. Note that the correctness of our algorithm does not rely on any unproven conjectures.

The pseudosquare upper L Subscript p is the smallest positive integer that is not a square, is 1 mod 8 , and is a quadratic residue modulo every odd prime q less-than-or-equal-to p .

Conjecture 1 (Bach and Huelsbergen Reference 3).

Let upper L Subscript p be the largest pseudosquare less-than-or-equal-to n . Then p equals upper O left-parenthesis log n log log n right-parenthesis .

Our second conjecture is needed to bound the cost of prime testing after sieving out by primes less-than-or-equal-to y in an arithmetic progression. Let p left-parenthesis n right-parenthesis denote the smallest prime divisor of the integer n .

Conjecture 2.

Let a comma b be positive integers with gcd left-parenthesis a comma b right-parenthesis equals 1 . Then

number-sign StartSet n less-than-or-equal-to x comma n identical-to a mod b comma p left-parenthesis n right-parenthesis greater-than y EndSet much-less-than StartFraction x Over b EndFraction product Underscript StartLayout 1st Row p less-than-or-equal-to y 2nd Row gcd left-parenthesis p comma b right-parenthesis equals 1 EndLayout Endscripts left-parenthesis 1 minus StartFraction 1 Over p EndFraction right-parenthesis period

This would be a theorem if b less-than-or-equal-to StartRoot x EndRoot ; see Reference 13, (1.7), (1.8); Reference 32.

We performed a few computations with this second version of our algorithm to show its practicality. A couple of these computational results are new.

The rest of this paper is organized as follows. In §2 we present our proof of Theorem 1, including our model of computation in §2.1, a description of our first algorithm in §2.2, and its running time analysis in §2.3. In §3 we discuss our second algorithm in §3.1 and its analysis in §3.2, thereby proving Theorem 2. We present our computational results in §4, including our work on twin primes in §4.1, our work on prime quadruplets in §4.2, and our results on Cunningham chains in §4.3. We wrap up with a discussion of possible future work in §5.

2. Theory

2.1. Model of computation

Our model of computation is a standard random access machine with infinite, direct-access memory. Memory can be addressed at the bit level or at the word level, and the word size is normal upper Theta left-parenthesis log n right-parenthesis bits if n is the input. Arithmetic operations on integers of upper O left-parenthesis log n right-parenthesis bits take constant time, as do memory/array accesses, comparisons, and other basic operations.

We count space used in bits, and we do not include the size of the output.

2.2. Our first algorithm

In this section we present the version of our algorithm with the smallest running time; we perform the analysis in the next section.

The input to the algorithm is the search bound n and the pattern, which consists of the value of k and the list of linear polynomials left-parenthesis f 1 left-parenthesis x right-parenthesis comma ellipsis comma f Subscript k Baseline left-parenthesis x right-parenthesis right-parenthesis . We write a Subscript i for the multiplier and b Subscript i for the offset for each form f Subscript i . For simplicity, we often assume that a 1 equals 1 and b 1 equals 0 , but this convenience is not required to obtain our complexity bound. So, for example, for Cunningham chains of the first kind we would have a 1 equals 1 comma a 2 equals 2 comma a 3 equals 4 comma ellipsis comma a Subscript k Baseline equals 2 Superscript k minus 1 and b 1 equals 0 comma b 2 equals 1 comma b 3 equals 3 comma ellipsis comma b Subscript k Baseline equals a Subscript k Baseline minus 1 .

(1)

We begin by finding the list of primes up to left floor StartRoot n EndRoot right floor and choosing a subset to be the wheel primes script upper W . Define upper W colon-equal product Underscript p element-of script upper W Endscripts p . Generally, we put all primes up to a bound y into script upper W , with y maximal such that upper W less-than-or-equal-to StartRoot n EndRoot . Then by the prime number theorem Reference 15 we have left-parenthesis 1 slash 2 right-parenthesis log n tilde log upper W equals sigma-summation Underscript p less-than-or-equal-to y Endscripts log p tilde y period

This implies that StartRoot n EndRoot slash log n much-less-than upper W less-than-or-equal-to StartRoot n EndRoot .

In practice, if there is a prime less-than-or-equal-to y that provides poor filtering for the pattern, we consider dropping it from script upper W and increasing y to include another prime.

We must also check all primes less-than-or-equal-to y to see if they participate in the prime pattern.

(2)

Next, we construct the wheel data structure so that it will generate all acceptable residues modulo upper W .

The data structure is initialized with a list of pairwise coprime moduli and for each such modulus m , a list of acceptable residues mod m , encoded as a bit vector of length m . The wheel modulus upper W is then the product of these moduli. Once initialized, the wheel has the ability to enumerate suitable residues modulo upper W in amortized constant time per residue. The residues do not appear in any particular order.

Therefore, for each prime p element-of script upper W we compute a bit vector (ones[]) that encodes the list of acceptable residues. For any integral x , we want f Subscript i Baseline left-parenthesis x right-parenthesis equals a Subscript i Baseline x plus b Subscript i to not be divisible by p . So if p divides a Subscript i Baseline x plus b Subscript i or, equivalently, if p does not divide a Subscript i and so x identical-to minus b Subscript i Baseline dot a Subscript i Superscript negative 1 Baseline mod p , then bit position x must be a zero.

Continuing the example above, for Cunningham chains of the first kind, p equals 3 gives the vector 001, and p equals 7 gives the vector 0010111.

We then construct the wheel data structure as described in Reference 28, §4.

(3)

For each residue r mod upper W generated by the wheel, we sieve k arithmetic progressions for primes up to n , f Subscript i Baseline left-parenthesis r right-parenthesis equals a Subscript i Baseline r plus b Subscript i Baseline mod upper W , or left-parenthesis a Subscript i Baseline r plus b Subscript i Baseline right-parenthesis plus j dot a Subscript i Baseline upper W for j equals 0 , …, left floor n slash left-parenthesis a Subscript i Baseline upper W right-parenthesis right floor . We do this using the Atkin-Bernstein sieve. (See Reference 2, §5 for how to use the sieve to find primes in an arithmetic progression.)

For each r , this yields k bit vectors of length less-than-or-equal-to n slash upper W which are combined using a bitwise AND operation to obtain the bit positions for where the pattern is satisfied by primes.

Example

Let us find the prime quadruplets ( k equals 4 , upper P equals left-parenthesis x comma x plus 2 comma x plus 6 comma x plus 8 right-parenthesis ) up to n equals 1000 using a wheel of size 2 dot 3 dot 5 dot 7 equals 210 .

We generate just the one quadruplet 5 comma 7 comma 11 comma 13 that contains wheel primes.

The only acceptable residue mod 2 is 1 , for 3 it is 2 (if x identical-to 1 mod 3 , then x plus 2 is divisible by 3 ), giving 5 mod 6 , and for 5 it is 1 , giving 11 mod 30 . For 7 there are three acceptable residues, 2 comma 3 comma 4 , giving us 11 comma 101 comma 191 mod 210 by the Chinese remainder theorem.

For r equals 11 mod 210 , we sieve the progression 11 plus j dot 210 for primes, getting the bit vector 10110; 11, 431, and 641 are prime, 221 and 851 are not. We then sieve r plus 2 equals 13 mod 210 for primes, getting 11111; they are all prime. Sieving r plus 6 equals 17 mod 210 gives 11011, and r plus 8 mod 210 gives 11101.

StartLayout 1st Row 1st Column 11 2nd Column CrossOut 221 EndCrossOut 3rd Column 431 4th Column 641 5th Column CrossOut 851 EndCrossOut 2nd Row 1st Column 13 2nd Column 223 3rd Column 433 4th Column 643 5th Column 853 3rd Row 1st Column 17 2nd Column 227 3rd Column CrossOut 437 EndCrossOut 4th Column 647 5th Column 857 4th Row 1st Column 19 2nd Column 229 3rd Column 439 4th Column CrossOut 649 EndCrossOut 5th Column 859 EndLayout

Bitwise AND-ing these four vectors together gives 10000. The only quadruplet we find is left-parenthesis 11 , 13 , 17 , 19 right-parenthesis .

Doing the same for r equals 101 , we get the following:

StartLayout 1st Row 1st Column 101 2nd Column 311 3rd Column 521 4th Column CrossOut 731 EndCrossOut 5th Column 941 2nd Row 1st Column 103 2nd Column 313 3rd Column 523 4th Column 733 5th Column CrossOut 943 EndCrossOut 3rd Row 1st Column 107 2nd Column 317 3rd Column CrossOut 527 EndCrossOut 4th Column CrossOut 737 EndCrossOut 5th Column 947 4th Row 1st Column 109 2nd Column CrossOut 319 EndCrossOut 3rd Column CrossOut 529 EndCrossOut 4th Column 739 5th Column CrossOut 949 EndCrossOut EndLayout

which gives us the quadruplet left-parenthesis 101 , 103 , 107 , 109 right-parenthesis .

Finally for r equals 191 we get

StartLayout 1st Row 1st Column 191 2nd Column 401 3rd Column CrossOut 611 EndCrossOut 4th Column 821 2nd Row 1st Column 193 2nd Column CrossOut 403 EndCrossOut 3rd Column 613 4th Column 823 3rd Row 1st Column 197 2nd Column CrossOut 407 EndCrossOut 3rd Column 617 4th Column 827 4th Row 1st Column 199 2nd Column 409 3rd Column 619 4th Column 829 EndLayout

and we get two quadruplets, left-parenthesis 191 , 193 , 197 , 199 right-parenthesis and left-parenthesis 821 , 823 , 827 , 829 right-parenthesis .

2.3. Complexity analysis

We’ll look at the cost for each step of the algorithm above.

(1)

We can use the Atkin-Bernstein sieve to find the primes up to StartRoot n EndRoot in upper O left-parenthesis StartRoot n EndRoot slash log log n right-parenthesis arithmetic operations using n Superscript 1 slash 4 space.

(2)

Recall that the largest wheel prime is roughly left-parenthesis 1 slash 2 right-parenthesis log n . Constructing the bit vector ones[] for one prime takes upper O left-parenthesis log n right-parenthesis time to initially write all ones and then upper O left-parenthesis k right-parenthesis time to mark the zeros. Summing over all wheel primes gives upper O left-parenthesis left-parenthesis log n right-parenthesis squared slash log log n right-parenthesis operations.

From Reference 28, Thm. 4.1 the total cost to build the wheel is upper O left-parenthesis left-parenthesis log n right-parenthesis cubed right-parenthesis operations, and it occupies upper O left-parenthesis left-parenthesis log n right-parenthesis cubed slash log log n right-parenthesis space.

(3)

The Atkin-Bernstein sieve finds all primes in an arithmetic progression in an interval of size StartRoot n EndRoot or larger in time linear in the length of the interval using space proportional to StartRoot n EndRoot Reference 2, §5. Therefore, sieving for primes takes upper O left-parenthesis n slash upper W right-parenthesis operations for each of the k residue classes f Subscript i Baseline left-parenthesis r right-parenthesis mod upper W , for a total of upper O left-parenthesis k n slash upper W right-parenthesis . The cost to generate each value of r using the wheel is negligible in comparison. The space used is upper O left-parenthesis k StartRoot n EndRoot right-parenthesis bits.

Next we show that the total number of residues is roughly asymptotic to upper W slash left-parenthesis log log n right-parenthesis Superscript k . For a pattern upper P of size k , all but finitely many primes p will have p minus k possible residues. Let b left-parenthesis upper P right-parenthesis be a constant, depending on the pattern upper P , such that all primes larger than b left-parenthesis upper P right-parenthesis have p minus k residues. Recall that y is a bound for the largest prime in the wheel. Then the total number of residues r mod upper W will be asymptotically bounded by StartLayout 1st Row 1st Column product Underscript p less-than-or-equal-to b left-parenthesis upper P right-parenthesis Endscripts p dot product Underscript b left-parenthesis upper P right-parenthesis less-than p less-than-or-equal-to y Endscripts left-parenthesis p minus k right-parenthesis 2nd Column less-than-or-equal-to 3rd Column upper W product Underscript b left-parenthesis upper P right-parenthesis less-than p less-than-or-equal-to y Endscripts StartFraction p minus k Over p EndFraction 2nd Row 1st Column Blank 2nd Column equals 3rd Column upper W product Underscript b left-parenthesis upper P right-parenthesis less-than p less-than-or-equal-to y Endscripts left-parenthesis 1 minus StartFraction k Over p EndFraction right-parenthesis period EndLayout

By Bernoulli’s inequality we have 1 minus k slash p less-than-or-equal-to left-parenthesis 1 minus 1 slash p right-parenthesis Superscript k , so that StartLayout 1st Row 1st Column upper W product Underscript b left-parenthesis upper P right-parenthesis less-than p less-than-or-equal-to y Endscripts left-parenthesis 1 minus StartFraction k Over p EndFraction right-parenthesis 2nd Column less-than-or-equal-to 3rd Column upper W product Underscript b left-parenthesis upper P right-parenthesis less-than p less-than-or-equal-to y Endscripts left-parenthesis 1 minus StartFraction 1 Over p EndFraction right-parenthesis Superscript k 2nd Row 1st Column Blank 2nd Column equals 3rd Column upper W product Underscript p less-than-or-equal-to b left-parenthesis upper P right-parenthesis Endscripts left-parenthesis 1 minus StartFraction 1 Over p EndFraction right-parenthesis Superscript negative k Baseline dot product Underscript p less-than-or-equal-to y Endscripts left-parenthesis 1 minus StartFraction 1 Over p EndFraction right-parenthesis Superscript k Baseline period EndLayout

The first product is bounded by a constant that depends on upper P , which we refer to as c left-parenthesis upper P right-parenthesis going forward. If y greater-than-or-equal-to 4 , then by Reference 26, (3.26) we know that product Underscript p less-than-or-equal-to y Endscripts left-parenthesis 1 minus StartFraction 1 Over p EndFraction right-parenthesis less-than StartFraction 1 Over log y EndFraction period

As shown above, if y is the largest prime in script upper W , we have y tilde left-parenthesis 1 slash 2 right-parenthesis log n . Asymptotically, y greater-than-or-equal-to left-parenthesis 1 slash 10 right-parenthesis log n is a very safe underestimate. Pulling this all together, we obtain the bound c left-parenthesis upper P right-parenthesis StartFraction upper W Over left-parenthesis log log n right-parenthesis Superscript k Baseline EndFraction

for the total number of residues r mod upper W .

Multiplying the sieving cost by the number of residues gives upper O left-parenthesis c left-parenthesis upper P right-parenthesis n slash left-parenthesis log log n right-parenthesis Superscript k Baseline right-parenthesis

operations.

We have proved Theorem 1.

It is possible to pin down c left-parenthesis upper P right-parenthesis , the constant that depends on upper P (and k ). We can use Reference 26, (3.30) and, assuming b left-parenthesis upper P right-parenthesis greater-than-or-equal-to 3 (note that b left-parenthesis upper P right-parenthesis greater-than-or-equal-to k ), we have

product Underscript p less-than-or-equal-to b left-parenthesis upper P right-parenthesis Endscripts StartFraction p Over p minus 1 EndFraction less-than 3.26 log b left-parenthesis upper P right-parenthesis period

Bringing in the factor of k introduced in the sieving, we have

c left-parenthesis upper P right-parenthesis less-than-or-equal-to k left-parenthesis 3.26 log b left-parenthesis upper P right-parenthesis right-parenthesis Superscript k Baseline period

It remains to get a bound for b left-parenthesis upper P right-parenthesis . Set upper A colon-equal max left-brace right-brace comma vertical-bar vertical-bar aj comma vertical-bar vertical-bar bj , an upper bound on all the coefficients in the pattern. Set upper F left-parenthesis x right-parenthesis colon-equal product Underscript i equals 1 Overscript k Endscripts f Subscript i Baseline left-parenthesis x right-parenthesis equals product Underscript i equals 1 Overscript k Endscripts left-parenthesis a Subscript i Baseline x plus b Subscript i Baseline right-parenthesis . For a prime p , if upper F has repeated roots modulo p , then p less-than-or-equal-to b left-parenthesis upper P right-parenthesis . But then a Subscript i Baseline x plus b Subscript i Baseline identical-to a Subscript j Baseline x plus b Subscript j Baseline mod p for some i comma j with i not-equals j , which means p divides a Subscript i Baseline b Subscript j minus a Subscript j Baseline b Subscript i , and hence p less-than-or-equal-to 2 upper A squared . Thus b left-parenthesis upper P right-parenthesis less-than-or-equal-to 2 upper A squared , and we have the bound

c left-parenthesis upper P right-parenthesis less-than-or-equal-to k left-parenthesis 3.26 log left-parenthesis 2 upper A squared right-parenthesis right-parenthesis Superscript k Baseline period

For specific patterns, the constant can be computed explicitly, typically giving much better results than this. In particular, we assumed every prime less-than-or-equal-to b left-parenthesis upper P right-parenthesis contributed all its residues (which happens if a prime divides all the a Subscript i ’s), which is unusual.

As an example, for our pattern upper P equals left-parenthesis x comma x plus 2 comma x plus 6 comma x plus 8 right-parenthesis , we have b left-parenthesis upper P right-parenthesis equals 3 , and our constant would be

4 dot left-parenthesis StartFraction 1 slash 2 Over left-parenthesis 1 minus 1 slash 2 right-parenthesis Superscript 4 Baseline EndFraction right-parenthesis left-parenthesis StartFraction 1 slash 3 Over left-parenthesis 1 minus 1 slash 3 right-parenthesis Superscript 4 Baseline EndFraction right-parenthesis equals 2 dot 3 cubed equals 54 period

Here the 1 slash 2 and 1 slash 3 multipliers are included because 2 and 3 have only one residue each instead of 2 and 3 , respectively.

Note that one of the anonymous referees deserves the primary credit for this bound on c left-parenthesis upper P right-parenthesis .

3. Practice

The primary difficulty in reaching large values of n with our first algorithm is the amount of space it requires. One way to address this is to create a larger wheel, sieve more but shorter arithmetic progressions for primes, and rely less on sieving and more on primality tests (in the style of Reference 28) when searching for k -tuples.

We use the sieve of Eratosthenes instead of the Atkin-Bernstein sieve for the arithmetic progressions, and this is the source of the log log n factor slowdown. The gains here are less space needed by a factor of k , and the effective trial division performs a quantifiable filtering out of non-primes.

Instead of sieving by all primes up to StartRoot n EndRoot , we sieve only by primes up to a bound upper B colon-equal n Superscript 1 slash c for a constant c greater-than 2 . In practice, we choose upper B so everything, including space for the wheel data structure, the bit vector for sieving, and the list of primes less-than-or-equal-to upper B , fits in CPU cache. We then use a base-2 pseudoprime test, followed by a prime test as needed. For smaller k , we use the pseudosquares prime test of Lukes, Patterson, and Williams Reference 21, which is fast and deterministic, assuming a sufficient table of pseudosquares is available. Importantly, it takes advantage of the trial division effect of the sieve of Eratosthenes. For larger k , we can simply use the AKS prime test Reference 1.

This change means we can get by with only upper O left-parenthesis upper B right-parenthesis space. Choosing upper B larger or smaller gives a tradeoff between the cost of sieving and the cost of performing base-2 pseudoprime tests.

3.1. Our second algorithm

(1)

Choose a constant c greater-than 2 , and then set upper B colon-equal 2 Superscript left floor left-parenthesis 1 slash c right-parenthesis log Super Subscript 2 Superscript n right floor , a power of 2 near n Superscript 1 slash c . We begin by finding the list of primes up to upper B and dividing them into the two sets script upper W and script upper S . Small primes go into script upper W and the remainder go in script upper S . We want upper W colon-equal product Underscript p element-of script upper W Endscripts p to be as large as possible with the constraint that upper W less-than-or-equal-to n slash upper B . This implies that the largest prime in script upper W will be roughly log n .

(2)

If k less-than-or-equal-to 6 , we will need to perform the pseudosquares prime test, so in preparation, find all pseudosquares upper L Subscript p Baseline less-than-or-equal-to n slash upper B (see Reference 21).

(3)

Next, as before, we construct the wheel data structure so that it will generate all possible correct residues modulo upper W .

(4)

For each residue r mod upper W generated by the wheel, we construct a bit vector v[] of length n slash upper W . Each vector position v[ j ], for j equals 0 , …, left floor upper W slash n right floor , represents x left-parenthesis j right-parenthesis equals r plus j dot upper W for the k -tuple left-parenthesis f 1 left-parenthesis x left-parenthesis j right-parenthesis right-parenthesis , f 2 left-parenthesis x left-parenthesis j right-parenthesis right-parenthesis , …, f Subscript k Baseline left-parenthesis x left-parenthesis j right-parenthesis right-parenthesis right-parenthesis . We initialize v[ j ] equals 1 but clear it to 0 if we find a prime p element-of script upper S where p bar f Subscript i Baseline left-parenthesis x left-parenthesis j right-parenthesis right-parenthesis for some i .

Once this sieving is complete, the only integers j with v[ j ] equals 1 that remain satisfy the property that all the f Subscript i Baseline left-parenthesis x left-parenthesis j right-parenthesis right-parenthesis have no prime divisors less than upper B .

(5)

For each such x left-parenthesis j right-parenthesis remaining (that is, v[ j ] equals 1 ), we first do a base-2 strong pseudoprime test on f 1 left-parenthesis x left-parenthesis j right-parenthesis right-parenthesis . If it fails, we cross it off (set v[ j ] equals 0 ). If it passes, we try f 2 left-parenthesis x right-parenthesis and so forth, keeping v[ j ] equals 1 only if all k values f Subscript i Baseline left-parenthesis x left-parenthesis j right-parenthesis right-parenthesis pass the pseudoprime test. We then perform a full prime test on the f Subscript i Baseline left-parenthesis x left-parenthesis j right-parenthesis right-parenthesis for all i . If k less-than-or-equal-to 6 , we use the Lukes, Patterson, and Williams pseudosquares prime test Reference 21 as done in Reference 28. For larger k , we use the AKS prime test Reference 1. (This is for the purposes of the theorem; in practice, the pseudosquares prime test is faster, so we use that instead.) If all the f Subscript i Baseline left-parenthesis x left-parenthesis j right-parenthesis right-parenthesis pass the prime tests, the corresponding k -tuple is written for output.

This version of the algorithm works best for k greater-than-or-equal-to 4 . When k less-than-or-equal-to 3 , the prime tests become the runtime bottleneck, and so we recommend using upper B equals StartRoot n EndRoot so that the base-2 pseudoprime tests and the pseudosquares prime test are not needed, as the sieving will leave only primes.

Example

We use the same example as above, finding prime quadruplets up to 5000 , which uses the pattern left-parenthesis x , x plus 2 , x plus 6 , x plus 8 right-parenthesis . We go a bit higher this time to illustrate the sieving. Recall that our wheel uses the primes 2 dot 3 dot 5 dot 7 and generates the three residues 11 , 101 , 191 modulo 210 .

We will use upper B equals 20 as our sieve bound, so script upper S equals left-brace 11 , 13 , 17 , 19 right-brace . As with the wheel primes, quadruplets that include sieve primes must be generated separately, so we output the quadruplet left-parenthesis 11 , 13 , 17 , 19 right-parenthesis at this point.

For r equals 11 , we have our progression

StartLayout 1st Row 1st Column 11 2nd Column 221 3rd Column 431 4th Column 641 5th Column 851 6th Column 1061 7th Column 1271 8th Column 1481 9th Column 1691 10th Column 1901 2nd Row 1st Column 2111 2nd Column 2321 3rd Column 2531 4th Column 2741 5th Column 2951 6th Column 3161 7th Column 3371 8th Column 3581 9th Column 3791 10th Column 4001 3rd Row 1st Column 4211 2nd Column 4421 3rd Column 4631 4th Column 4841 EndLayout

For p equals 11 , we cross off integers that are 0 , 3 , 5 , 9 modulo 11 . This takes four passes: on the first pass we remove 11 , 2321 , 4631 , which are 0 mod 11 ; on the second pass we remove 641 , 2951 , which are 3 mod 11 (for example 649 equals 11 dot 59 ); the third removes 1061 , 3371 , which are 5 mod 11 ; and the fourth removes 1901 , 4211 , which are 9 mod 11 . Observe that for a given residue modulo 11 , the numbers to cross off are exactly 11 spaces apart.

StartLayout 1st Row 1st Column CrossOut 11 EndCrossOut 2nd Column 221 3rd Column 431 4th Column CrossOut 641 EndCrossOut 5th Column 851 6th Column CrossOut 1061 EndCrossOut 7th Column 1271 8th Column 1481 9th Column 1691 10th Column CrossOut 1901 EndCrossOut 2nd Row 1st Column 2111 2nd Column CrossOut 2321 EndCrossOut 3rd Column 2531 4th Column 2741 5th Column CrossOut 2951 EndCrossOut 6th Column 3161 7th Column CrossOut 3371 EndCrossOut 8th Column 3581 9th Column 3791 10th Column 4001 3rd Row 1st Column CrossOut 4211 EndCrossOut 2nd Column 4421 3rd Column CrossOut 4631 EndCrossOut 4th Column 4841 EndLayout

For p equals 13 , we cross off integers that are 0 , 5 , 7 , 11 modulo 13 . We remove 221 , 2951 for 0 mod 13 , 2111 , 4841 for 5 mod 13 , 2321 for 7 mod 13 , and 11 , 2741 for 11 mod 13 .

StartLayout 1st Row 1st Column CrossOut 11 EndCrossOut 2nd Column CrossOut 221 EndCrossOut 3rd Column 431 4th Column CrossOut 641 EndCrossOut 5th Column 851 6th Column CrossOut 1061 EndCrossOut 7th Column 1271 8th Column 1481 9th Column 1691 10th Column CrossOut 1901 EndCrossOut 2nd Row 1st Column CrossOut 2111 EndCrossOut 2nd Column CrossOut 2321 EndCrossOut 3rd Column 2531 4th Column CrossOut 2741 EndCrossOut 5th Column CrossOut 2951 EndCrossOut 6th Column 3161 7th Column CrossOut 3371 EndCrossOut 8th Column 3581 9th Column 3791 10th Column 4001 3rd Row 1st Column CrossOut 4211 EndCrossOut 2nd Column 4421 3rd Column CrossOut 4631 EndCrossOut 4th Column CrossOut 4841 EndCrossOut EndLayout

For p equals 17 , we cross off integers that are 0 , 9 , 11 , 15 modulo 17 . We remove 221 , 3791 for 0 mod 17 , 2321 for 9 mod 17 , 2531 for 15 mod 17 , and 11 , 3581 for 11 mod 17 .

StartLayout 1st Row 1st Column CrossOut 11 EndCrossOut 2nd Column CrossOut 221 EndCrossOut 3rd Column 431 4th Column CrossOut 641 EndCrossOut 5th Column 851 6th Column CrossOut 1061 EndCrossOut 7th Column 1271 8th Column 1481 9th Column 1691 10th Column CrossOut 1901 EndCrossOut 2nd Row 1st Column CrossOut 2111 EndCrossOut 2nd Column CrossOut 2321 EndCrossOut 3rd Column CrossOut 2531 EndCrossOut 4th Column CrossOut 2741 EndCrossOut 5th Column CrossOut 2951 EndCrossOut 6th Column 3161 7th Column CrossOut 3371 EndCrossOut 8th Column CrossOut 3581 EndCrossOut 9th Column CrossOut 3791 EndCrossOut 10th Column 4001 3rd Row 1st Column CrossOut 4211 EndCrossOut 2nd Column 4421 3rd Column CrossOut 4631 EndCrossOut 4th Column CrossOut 4841 EndCrossOut EndLayout

For p equals 19 , we cross off integers that are 0 , 11 , 13 , 17 modulo 19 . We remove 11 , 4001 for 11 mod 19 , 431 , 4421 for 13 mod 19 , 1271 for 17 mod 19 , and 1691 for 0 mod 19 .

StartLayout 1st Row 1st Column CrossOut 11 EndCrossOut 2nd Column CrossOut 221 EndCrossOut 3rd Column CrossOut 431 EndCrossOut 4th Column CrossOut 641 EndCrossOut 5th Column 851 6th Column CrossOut 1061 EndCrossOut 7th Column CrossOut 1271 EndCrossOut 8th Column 1481 9th Column CrossOut 1691 EndCrossOut 10th Column CrossOut 1901 EndCrossOut 2nd Row 1st Column CrossOut 2111 EndCrossOut 2nd Column CrossOut 2321 EndCrossOut 3rd Column CrossOut 2531 EndCrossOut 4th Column CrossOut 2741 EndCrossOut 5th Column CrossOut 2951 EndCrossOut 6th Column 3161 7th Column CrossOut 3371 EndCrossOut 8th Column CrossOut 3581 EndCrossOut 9th Column CrossOut 3791 EndCrossOut 10th Column CrossOut 4001 EndCrossOut 3rd Row 1st Column CrossOut 4211 EndCrossOut 2nd Column CrossOut 4421 EndCrossOut 3rd Column CrossOut 4631 EndCrossOut 4th Column CrossOut 4841 EndCrossOut EndLayout

At this point we perform base-2 strong pseudoprime tests, followed by prime tests as needed. Here 851 and 3161 are not prime, and 1481 leads to the quadruplet left-parenthesis 1481 , 1483 , 1487 , 1489 right-parenthesis .

This is then repeated with r equals 101 , 191 .

3.2. Complexity analysis

Finding the primes up to upper B takes upper O left-parenthesis upper B right-parenthesis time using upper O left-parenthesis StartRoot upper B EndRoot right-parenthesis space, well within our bounds. See Reference 28 for a sublinear time algorithm to find all needed pseudosquares. In practice, all pseudosquares up to 10 Superscript 25 are known Reference 29. The cost in time and space to build the wheel is, up to a constant factor, the same. So we now focus on steps (4) and (5).

As shown above, the number of residues to check mod upper W is upper O Subscript upper P Baseline left-parenthesis upper W slash left-parenthesis log log n right-parenthesis Superscript k Baseline right-parenthesis . The time to sieve each interval of length n slash upper W using primes up to upper B is at most proportional to

sigma-summation Underscript p less-than-or-equal-to upper B Endscripts StartFraction k n Over p upper W EndFraction tilde StartFraction k n log log upper B Over upper W EndFraction tilde StartFraction k n log log n Over upper W EndFraction period

Here the multiplier k is required because we cross off k residues modulo most of the primes p less-than-or-equal-to upper B . That said, this multiple of k can be absorbed into the implied constant that depends on the pattern upper P , c left-parenthesis upper P right-parenthesis , from earlier.

At this point we make use of Conjecture 2 to bound the number of integers free from prime divisors less-than-or-equal-to upper B in an arithmetic progression.

With this assumption in hand, by Mertens’s theorem, an average of at most

StartFraction n Over upper W EndFraction product Underscript y less-than p less-than-or-equal-to upper B Endscripts left-parenthesis 1 minus StartFraction 1 Over p EndFraction right-parenthesis much-less-than StartFraction n log y Over upper W log upper B EndFraction tilde StartFraction n log log n Over upper W log n EndFraction

vector locations remain to be prime tested. (Note that we cannot make any assumptions about the relative independence of the primality of the f Subscript i Baseline left-parenthesis x right-parenthesis values for different i , and so we cannot use a left-parenthesis 1 minus k slash p right-parenthesis factor here.)

A single base-2 strong pseudoprime test takes upper O left-parenthesis log n right-parenthesis operations to perform, for a total cost proportional to

StartFraction k n log log n Over upper W log n EndFraction log n tilde StartFraction k n log log n Over upper W EndFraction

arithmetic operations to do the base-2 strong pseudoprime tests for each value of r mod upper W . This matches the sieving cost of upper O Subscript upper P Baseline left-parenthesis n log log n slash upper W right-parenthesis from above. (Note that if we deliberately choose a larger value for upper B , the increased sieving will decrease the number of pseudoprime tests needed. This tradeoff can be used to fine-tune the running time of the algorithm.)

Thus, the total cost for sieving and base-2 pseudoprime tests is

upper O Subscript upper P Baseline left-parenthesis StartFraction n Over left-parenthesis log log n right-parenthesis Superscript k minus 1 Baseline EndFraction right-parenthesis comma

which we obtain by multiplying by the number of residues upper O Subscript upper P Baseline left-parenthesis upper W slash left-parenthesis log log n right-parenthesis Superscript k Baseline right-parenthesis .

Next we need to count integers that pass the base-2 strong pseudoprime test. Such integers are either prime or composite base-2 pseudoprimes. We switch to counting across all residues r mod upper W to obtain an overall bound.

Lemma 1 tells us that at most upper O left-parenthesis n slash left-parenthesis log n right-parenthesis Superscript k Baseline right-parenthesis integers are prime that fit the pattern, so this is an upper bound on primes that pass the base-2 pseudoprime test.

Pomerance Reference 24 showed that the number of composite base-2 pseudoprimes less-than-or-equal-to n is bounded by

n e Superscript minus StartRoot StartFraction log n log log log n Over log log n EndFraction EndRoot Baseline much-less-than StartFraction n Over left-parenthesis log n right-parenthesis Superscript k plus 1 Baseline EndFraction comma

which is negligible. This plus the bound for primes above gives us the upper O left-parenthesis n slash left-parenthesis log n right-parenthesis Superscript k Baseline right-parenthesis bound we desire for all integers that pass the base-2 pseudoprime test.

Next, to bound the cost of prime tests, we have two cases: k greater-than 6 or 2 less-than k less-than-or-equal-to 6 .

For k greater-than 6 , we use the AKS prime test Reference 1 (improved in Reference 19) which takes time upper O left-parenthesis left-parenthesis log n right-parenthesis Superscript 6 plus o left-parenthesis 1 right-parenthesis Baseline right-parenthesis . The cost of applying the AKS prime test to all the integers f Subscript i Baseline left-parenthesis x right-parenthesis after they all pass a base-2 pseudoprime test is at most proportional to

k dot left-parenthesis log n right-parenthesis Superscript 6 plus o left-parenthesis 1 right-parenthesis Baseline dot StartFraction n Over left-parenthesis log n right-parenthesis Superscript k Baseline EndFraction much-less-than StartFraction k n Over left-parenthesis log n right-parenthesis Superscript k minus 6 plus o left-parenthesis 1 right-parenthesis Baseline EndFraction comma

which is o left-parenthesis k n slash left-parenthesis log log n right-parenthesis Superscript k Baseline right-parenthesis for k greater-than 6 .

Note that when k is large, in practice we might only do the base-2 pseudoprime tests and then run full prime tests on the output afterwards, since the amount of output will be rather small.

For 2 less-than k less-than-or-equal-to 6 , Conjecture 1 implies that the pseudosquares prime test takes upper O left-parenthesis left-parenthesis log n right-parenthesis squared right-parenthesis arithmetic operations to test integers less-than-or-equal-to n for primality, given a table of pseudosquares less-than-or-equal-to n . If n has no prime divisors below upper B , then pseudosquares up to n slash upper B suffice. See Reference 21Reference 28.

So, under the assumption of Conjecture 1, the cost of applying the pseudosquares prime test to all the integers f Subscript i Baseline left-parenthesis x right-parenthesis after they all pass a base-2 pseudoprime test is at most proportional to

k dot left-parenthesis log n right-parenthesis squared dot StartFraction n Over left-parenthesis log n right-parenthesis Superscript k Baseline EndFraction much-less-than StartFraction k n Over left-parenthesis log n right-parenthesis Superscript k minus 2 Baseline EndFraction comma

and this is o left-parenthesis k n slash left-parenthesis log log n right-parenthesis Superscript k Baseline right-parenthesis for k greater-than 2 .

The space used is dominated by the length of the sieve intervals and the space needed to store the primes in script upper S , which is upper O left-parenthesis upper B right-parenthesis bits.

This completes the proof of Theorem 2.

4. Computations

As mentioned previously, we implemented several versions of our second algorithm to see what we could compute. We looked for new computational records that were within reach of our university’s nice but aging hardware. Below we discuss some of the results of those computations. Some of the implementation details are specific to a particular computation. Here are four remarks about implementation details that these computations had in common.

(1)

We wrote our programs in C++ using the GNU compiler under Linux. GMP was used for multiprecision arithmetic when necessary. Note that it was fairly easy to write the code such that GMP was needed only on occasion and for prime tests.

(2)

We used MPI and ran our code on Butler University’s cluster Big Dawg. This machine has 16 compute nodes with 12 cores (2 CPUS), each at optimal capacity. Our average utilization was around 150 of the 192 cores due to compute nodes going down from time to time. The CPU is the Intel Xeon CPU E5-2630 0 @ 2.30GHz with 15 MB cache, with 6 cores per CPU.

To parallelize the algorithm, we striped on the residues r mod upper W . In other words, all nu processors stepped through all the r mod upper W residues but only sieved every nu th residue for primes. This meant there was very little communication overhead, except for when periodic checkpoints were done, about every 15-30 minutes.

(3)

We usually chose our wheel size ( upper W ) and sieve intervals so that the size of each interval ( n slash upper W almost-equals upper B ) was at most a few megabytes so that it would fit in the CPU cache. We used a vector<bool>, which packs bits.

(4)

For larger values of k , we observed that when sieving by smaller primes p by each of the k residues, we might find that almost all the bits of the current interval were cleared long before we reached the sieving limit upper B , so we created a simple early-abort strategy that was able to save time.

The very few remaining bits were tested with the base-2 strong pseudoprime test even though we had not sieved all the way to upper B . We also, then, replaced the use of the pseudosquares prime test with strong pseudoprime tests Reference 22 using results from Reference 30 so that only a few bases were needed, due to the spotty trial-division information.

(5)

We found that, especially for larger k , our algorithm spent more time on sieving than prime testing. As mentioned previously, for k equals 3 the prime testing dominates the running time in practice, and it is worthwhile to use upper B equals StartRoot n EndRoot so that prime testing is not required.

4.1. Twin primes and Brun’s constant

Let pi 2 left-parenthesis upper X right-parenthesis count the twin prime pairs left-parenthesis p comma p plus 2 right-parenthesis with p less-than upper X and let upper S 2 left-parenthesis upper X right-parenthesis be the sum of the reciprocals of their elements. Thomas Nicely computed these functions up to 2 dot 10 Superscript 16 (see http://www.trnicely.net/\#PI2X). We verified his computations to 14 digits and extended the results to upper X equals 10 Superscript 17 . A portion of our computational results are in the table below.

upper X pi 2 left-parenthesis x right-parenthesis upper S 2 left-parenthesis upper X right-parenthesis
1 dot 10 Superscript 16 10304195697298 1.8304844246583
2 dot 10 Superscript 16 19831847025792 1.8318080634324
3 dot 10 Superscript 16 29096690339843 1.8325599218628
4 dot 10 Superscript 16 38196843833352 1.8330837014776
5 dot 10 Superscript 16 47177404870103 1.8334845790134
6 dot 10 Superscript 16 56064358236032 1.8338086822020
7 dot 10 Superscript 16 64874581322443 1.8340803303554
8 dot 10 Superscript 16 73619911145552 1.8343139034256
9 dot 10 Superscript 16 82309090712061 1.8345186031523
10 dot 10 Superscript 16 90948839353159 1.8347006694414

The last section of Klyve’s PhD thesis Reference 18 describes how to use this information to derive bounds for Brun’s constant.

We have four remarks on our algorithm implementation:

(1)

As mentioned above, for small k like k equals 2 , it is more efficient to set upper B equals StartRoot n EndRoot so that sieving also determines primality, thereby avoiding base-2 strong pseudoprime tests and primality tests.

(2)

We computed upper S 2 using Kahan summation Reference 17 with the long double data type in C++, which gave us 17 digits, 14 of which were accurate; Thomas Nicely has data with 53 digits of accuracy. The partial sums were accumulated in 10,000 buckets for each process, and then the buckets were in turn added up across processes using Kahan summation.

(3)

Our computation took roughly 3 weeks of wall time, which included at least one restart from a checkpoint. Our verification of Nicely’s work to 10 Superscript 16 took 42 hours.

(4)

We used a wheel with upper W equals 6469693230 equals 2 dot 3 dot 5 dot 7 dot 11 dot 13 dot 17 dot 19 dot 23 dot 29 . Note that this is roughly 20 dot StartRoot 10 Superscript 17 Baseline EndRoot . There were 214708725 residues r mod upper W to sieve.

See OEIS.org sequence A007508, the number of twin prime pairs below 10 Superscript n .

4.2. Quadruplet primes

A related sum involves the reciprocals of the elements of the prime tuple left-parenthesis p comma p plus 2 comma p plus 6 comma p plus 8 right-parenthesis . Let pi 4 left-parenthesis upper X right-parenthesis count these tuplets up to upper X , and let upper S 4 left-parenthesis upper X right-parenthesis be the sum of the reciprocals of their elements. Thomas Nicely computed these functions up to 2 dot 10 Superscript 16 . We extended this computation and partial results are in the table below. The first two lines are Thomas Nicely’s own results, which we verified.

upper X pi 4 left-parenthesis x right-parenthesis upper S 4 left-parenthesis upper X right-parenthesis
1 dot 10 Superscript 16 25379433651 0.8704776912340
2 dot 10 Superscript 16 46998268431 0.8704837109481
3 dot 10 Superscript 16 67439513530 0.8704870310432
4 dot 10 Superscript 16 87160212807 0.8704893020026
5 dot 10 Superscript 16 106365371168 0.8704910169467
6 dot 10 Superscript 16 125172360474 0.8704923889088
7 dot 10 Superscript 16 143655957845 0.8704935288452
8 dot 10 Superscript 16 161868188061 0.8704945017556
9 dot 10 Superscript 16 179847459283 0.8704953489172
10 dot 10 Superscript 16 197622677481 0.8704960981105

This computation took about 4 days, and we used a separate program rather than looking for pairs of twin primes in the first program. Even though k equals 4 is large enough to use prime tests, we found that sieving to StartRoot n EndRoot was faster in practice.

We used a wheel with upper W equals 200560490130 equals 2 dot 3 dot 5 dot 7 dot 11 dot 13 dot 17 dot 19 dot 23 dot 29 dot 31 , which gave 472665375 residues.

See OEIS.org sequence A050258, the number of prime quadruplets with largest member less-than 10 Superscript n .

4.3. Cunningham chains

We have two new computational results for Cunningham chains.

(1)

We found the smallest chain of length 15 of the first kind, and it begins with the primep equals 90616 21195 84658 42219 period

The next four chains of this length of the first kind begin with StartLayout 1st Row 1 13220 80067 50697 84839 2nd Row 1 13710 75635 40868 11919 3rd Row 1 23068 71734 48294 53339 4th Row 1 40044 19781 72085 69169 EndLayout

This computation took roughly a month of wall time. Here we used wheel size upper W equals 19835154277048110 equals 2 dot 3 dot 5 dot 7 dot 11 dot 13 dot 17 dot 19 dot 23 dot 29 dot 37 dot 41 dot 43 dot 47 , with 12841500672 residues to sieve. Note that 31 is a rather badly behaved prime for larger Cunningham chains (only 5 residues are excluded), so we left it out of the wheel.

See OEIS.org sequence A005602, smallest prime beginning a Cunningham chain of length n (of the first kind).

(2)

In 2008 Jaroslaw Wroblewski found a Cunningham chain of length 17 of the first kind, starting withp equals 27 59832 93417 13865 93519 comma

and we were able to show that this is in fact the smallest such chain of that length.

This computation took roughly three months of wall time. We used upper W equals 1051263176683549830 equals 2 dot 3 dot 5 dot 7 dot 11 dot 13 dot 17 dot 19 dot 23 dot 29 dot 37 dot 41 dot 43 dot 47 dot 53 , with 35864945424 residues to sieve. With roughly three times as many residues as the previous computation, it took roughly three times as long to complete.

5. Discussion and future work

In summary, we have described and analyzed two algorithms for finding primes in patterns and then shown that the second of these algorithms is quite practical by performing a few computations.

We have some ideas for future work.

(1)

In the Introduction, we mentioned that our algorithms could be used to find Carmichael numbers by finding prime triplets that satisfy the pattern left-parenthesis 6 x plus 1 , 12 x plus 1 , 18 x plus 1 right-parenthesis , but we have not yet done that computation Reference 6.

(2)

Does it make sense to use Bernstein’s doubly focused enumeration to attempt to further reduce the running time? See Reference 5Reference 29Reference 31.

(3)

A natural extension to our algorithms here is to allow the linear polynomials f Subscript i to potentially be higher degree, irreducible polynomials. See Schinzel’s Hypothesis H. (See Reference 27 and Reference 7, §1.2.2) and the Bateman-Horn conjecture Reference 4.)

(4)

An algorithm for twin primes with space roughly n Superscript 1 slash 3 that runs in upper O left-parenthesis n slash left-parenthesis log log n right-parenthesis squared right-parenthesis time would be nice.

Acknowledgments

We wish to thank Frank Levinson for his generous gift that funds the Butler cluster supercomputer Big Dawg and the Holcomb Awards Committee for their financial support of this work.

Thanks to Thomàs Oliveira e Silva for several helpful comments on an earlier version of this paper.

We also wish to thank two anonymous referees for many detailed, helpful comments on earlier versions of this paper. In particular, one of the referees contributed the analysis of the implied constant in §2.3.

Mathematical Fragments

Lemma 1.

Given an admissible pattern left-parenthesis f 1 left-parenthesis x right-parenthesis comma ellipsis comma f Subscript k Baseline left-parenthesis x right-parenthesis right-parenthesis of length k , the number of integers x such that the f Subscript i Baseline left-parenthesis x right-parenthesis are all simultaneously prime and max left-brace f Subscript i Baseline left-parenthesis x right-parenthesis right-brace less-than-or-equal-to n is upper O left-parenthesis n slash left-parenthesis log n right-parenthesis Superscript k Baseline right-parenthesis .

Theorem 1.

There is an algorithm that when given a list of k distinct linear polynomials over the integers, with positive leading coefficients, upper P equals left-parenthesis f 1 left-parenthesis x right-parenthesis comma ellipsis comma f Subscript k Baseline left-parenthesis x right-parenthesis right-parenthesis (the pattern), and a search bound n finds all integers x such that max left-brace f Subscript i Baseline left-parenthesis x right-parenthesis right-brace less-than-or-equal-to n and all the f Subscript i Baseline left-parenthesis x right-parenthesis are prime. This algorithm uses at most upper O Subscript upper P Baseline left-parenthesis n slash left-parenthesis log log n right-parenthesis Superscript k Baseline right-parenthesis arithmetic operations and upper O left-parenthesis k StartRoot n EndRoot right-parenthesis bits of space.

Theorem 2.

Let c greater-than 2 . There is an algorithm that when given a list of k greater-than 2 distinct linear polynomials over the integers, with positive leading coefficients, upper P equals left-parenthesis f 1 left-parenthesis x right-parenthesis comma ellipsis comma f Subscript k Baseline left-parenthesis x right-parenthesis right-parenthesis (the pattern), and a search bound n finds all integers x such that max left-brace f Subscript i Baseline left-parenthesis x right-parenthesis right-brace less-than-or-equal-to n and all the f Subscript i Baseline left-parenthesis x right-parenthesis are prime. This algorithm uses at most upper O Subscript upper P Baseline left-parenthesis n slash left-parenthesis log log n right-parenthesis Superscript k minus 1 Baseline right-parenthesis arithmetic operations and n Superscript 1 slash c bits of space, under the assumption of Conjectures 1 and 2 (see below). Correctness of the output is unconditional.

Conjecture 1 (Bach and Huelsbergen Reference 3).

Let upper L Subscript p be the largest pseudosquare less-than-or-equal-to n . Then p equals upper O left-parenthesis log n log log n right-parenthesis .

Conjecture 2.

Let a comma b be positive integers with gcd left-parenthesis a comma b right-parenthesis equals 1 . Then

number-sign StartSet n less-than-or-equal-to x comma n identical-to a mod b comma p left-parenthesis n right-parenthesis greater-than y EndSet much-less-than StartFraction x Over b EndFraction product Underscript StartLayout 1st Row p less-than-or-equal-to y 2nd Row gcd left-parenthesis p comma b right-parenthesis equals 1 EndLayout Endscripts left-parenthesis 1 minus StartFraction 1 Over p EndFraction right-parenthesis period

References

[1]
M. Agrawal, N. Kayal, and N. Saxena, PRIMES is in P, Ann. of Math. (2) 160 (2004), no. 2, 781–793, DOI 10.4007/annals.2004.160.781. MR2123939, Show rawAMSref\bib{AKS04}{article}{ author={Agrawal, Manindra}, author={Kayal, Neeraj}, author={Saxena, Nitin}, title={PRIMES is in P}, journal={Ann. of Math. (2)}, volume={160}, date={2004}, number={2}, pages={781--793}, issn={0003-486X}, review={\MR {2123939}}, doi={10.4007/annals.2004.160.781}, } Close amsref.
[2]
A. O. L. Atkin and D. J. Bernstein, Prime sieves using binary quadratic forms, Math. Comp. 73 (2004), no. 246, 1023–1030, DOI 10.1090/S0025-5718-03-01501-1. MR2031423, Show rawAMSref\bib{AB2004}{article}{ author={Atkin, A. O. L.}, author={Bernstein, D. J.}, title={Prime sieves using binary quadratic forms}, journal={Math. Comp.}, volume={73}, date={2004}, number={246}, pages={1023--1030}, issn={0025-5718}, review={\MR {2031423}}, doi={10.1090/S0025-5718-03-01501-1}, } Close amsref.
[3]
E. Bach and L. Huelsbergen, Statistical evidence for small generating sets, Math. Comp. 61 (1993), no. 203, 69–82, DOI 10.2307/2152936. MR1195432, Show rawAMSref\bib{BH93}{article}{ author={Bach, Eric}, author={Huelsbergen, Lorenz}, title={Statistical evidence for small generating sets}, journal={Math. Comp.}, volume={61}, date={1993}, number={203}, pages={69--82}, issn={0025-5718}, review={\MR {1195432}}, doi={10.2307/2152936}, } Close amsref.
[4]
P. T. Bateman and R. A. Horn, A heuristic asymptotic formula concerning the distribution of prime numbers, Math. Comp. 16 (1962), 363–367, DOI 10.2307/2004056. MR148632, Show rawAMSref\bib{BH62}{article}{ author={Bateman, Paul T.}, author={Horn, Roger A.}, title={A heuristic asymptotic formula concerning the distribution of prime numbers}, journal={Math. Comp.}, volume={16}, date={1962}, pages={363--367}, issn={0025-5718}, review={\MR {148632}}, doi={10.2307/2004056}, } Close amsref.
[5]
D. J. Bernstein, Doubly focused enumeration of locally square polynomial values, High Primes and Misdemeanours: Lectures in Honour of the 60th Birthday of Hugh Cowie Williams, Fields Inst. Commun., vol. 41, Amer. Math. Soc., Providence, RI, 2004, pp. 69–76. MR2075648, Show rawAMSref\bib{Bernstein04}{article}{ author={Bernstein, Daniel J.}, title={Doubly focused enumeration of locally square polynomial values}, conference={ title={High Primes and Misdemeanours: Lectures in Honour of the 60th Birthday of Hugh Cowie Williams}, }, book={ series={Fields Inst. Commun.}, volume={41}, publisher={Amer. Math. Soc., Providence, RI}, }, date={2004}, pages={69--76}, review={\MR {2075648}}, } Close amsref.
[6]
J. Chernick, On Fermat’s simple theorem, Bull. Amer. Math. Soc. 45 (1939), no. 4, 269–274, DOI 10.1090/S0002-9904-1939-06953-X. MR1563964, Show rawAMSref\bib{Chernick39}{article}{ author={Chernick, Jack}, title={On Fermat's simple theorem}, journal={Bull. Amer. Math. Soc.}, volume={45}, date={1939}, number={4}, pages={269--274}, issn={0002-9904}, review={\MR {1563964}}, doi={10.1090/S0002-9904-1939-06953-X}, } Close amsref.
[7]
R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, Springer-Verlag, New York, 2001. MR1821158, Show rawAMSref\bib{CP}{book}{ author={Crandall, Richard}, author={Pomerance, Carl}, title={Prime Numbers}, subtitle={A Computational Perspective}, publisher={Springer-Verlag, New York}, date={2001}, pages={xvi+545}, isbn={0-387-94777-9}, review={\MR {1821158}}, doi={10.1007/978-1-4684-9316-0}, } Close amsref.
[8]
L. E. Dickson, A new extension of Dirichlet’s theorem on prime numbers, Messenger of Mathematics 33 (1904), 155–161.
[9]
T. Forbes, Prime clusters and Cunningham chains, Math. Comp. 68 (1999), no. 228, 1739–1747, DOI 10.1090/S0025-5718-99-01117-5. MR1651752, Show rawAMSref\bib{Forbes99}{article}{ author={Forbes, Tony}, title={Prime clusters and Cunningham chains}, journal={Math. Comp.}, volume={68}, date={1999}, number={228}, pages={1739--1747}, issn={0025-5718}, review={\MR {1651752}}, doi={10.1090/S0025-5718-99-01117-5}, } Close amsref.
[10]
W. F. Galway, Dissecting a sieve to cut its need for space, Algorithmic Number Theory (Leiden, 2000), Lecture Notes in Comput. Sci., vol. 1838, Springer, Berlin, 2000, pp. 297–312, DOI 10.1007/10722028_17. MR1850613, Show rawAMSref\bib{Galway2000}{article}{ author={Galway, William F.}, title={Dissecting a sieve to cut its need for space}, conference={ title={Algorithmic Number Theory}, address={Leiden}, date={2000}, }, book={ series={Lecture Notes in Comput. Sci.}, volume={1838}, publisher={Springer, Berlin}, }, date={2000}, pages={297--312}, review={\MR {1850613}}, doi={10.1007/10722028\_17}, } Close amsref.
[11]
D. M. Gordon and G. Rodemich, Dense admissible sets, Algorithmic Number Theory (Portland, OR, 1998), Lecture Notes in Comput. Sci., vol. 1423, Springer, Berlin, 1998, pp. 216–225, DOI 10.1007/BFb0054864. MR1726073, Show rawAMSref\bib{GR98}{article}{ author={Gordon, Daniel M.}, author={Rodemich, Gene}, title={Dense admissible sets}, conference={ title={Algorithmic Number Theory}, address={Portland, OR}, date={1998}, }, book={ series={Lecture Notes in Comput. Sci.}, volume={1423}, publisher={Springer, Berlin}, }, date={1998}, pages={216--225}, review={\MR {1726073}}, doi={10.1007/BFb0054864}, } Close amsref.
[12]
R. K. Guy, Unsolved Problems in Number Theory, 3rd ed., Problem Books in Mathematics, Springer-Verlag, New York, 2004. MR2076335, Show rawAMSref\bib{UPINT}{book}{ author={Guy, Richard K.}, title={Unsolved Problems in Number Theory}, series={Problem Books in Mathematics}, edition={3}, publisher={Springer-Verlag, New York}, date={2004}, pages={xviii+437}, isbn={0-387-20860-7}, review={\MR {2076335}}, doi={10.1007/978-0-387-26677-0}, } Close amsref.
[13]
H. Halberstam and H.-E. Richert, Sieve Methods, London Mathematical Society Monographs, No. 4, Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], London-New York, 1974. MR0424730, Show rawAMSref\bib{HR}{book}{ author={Halberstam, H.}, author={Richert, H.-E.}, title={Sieve Methods}, edition={London Mathematical Society Monographs, No. 4}, publisher={Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], London-New York}, date={1974}, pages={xiv+364 pp. (loose errata)}, review={\MR {0424730}}, } Close amsref.
[14]
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 (1923), no. 1, 1–70, DOI 10.1007/BF02403921. MR1555183, Show rawAMSref\bib{HL23}{article}{ author={Hardy, G. H.}, author={Littlewood, J. E.}, title={Some problems of `Partitio numerorum'; III: On the expression of a number as a sum of primes}, journal={Acta Math.}, volume={44}, date={1923}, number={1}, pages={1--70}, issn={0001-5962}, review={\MR {1555183}}, doi={10.1007/BF02403921}, } Close amsref.
[15]
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., The Clarendon Press, Oxford University Press, New York, 1979. MR568909, Show rawAMSref\bib{HW}{book}{ author={Hardy, G. H.}, author={Wright, E. M.}, title={An Introduction to the Theory of Numbers}, edition={5}, publisher={The Clarendon Press, Oxford University Press, New York}, date={1979}, pages={xvi+426}, isbn={0-19-853170-2}, isbn={0-19-853171-0}, review={\MR {568909}}, } Close amsref.
[16]
H. A. Helfgott, An improved sieve of Eratosthenes, Math. Comp. 89 (2020), no. 321, 333–350, DOI 10.1090/mcom/3438. MR4011545, Show rawAMSref\bib{Helfgott2020}{article}{ author={Helfgott, Harald Andr\'{e}s}, title={An improved sieve of Eratosthenes}, journal={Math. Comp.}, volume={89}, date={2020}, number={321}, pages={333--350}, issn={0025-5718}, review={\MR {4011545}}, doi={10.1090/mcom/3438}, } Close amsref.
[17]
W. Kahan, Pracniques: Further remarks on reducing truncation errors, Commun. ACM 8 (1965), no. 1, 40ff.
[18]
D. Klyve, Explicit bounds on twin primes and Brun’s constant, ProQuest LLC, Ann Arbor, MI. Thesis (Ph.D.)–Dartmouth College, 2007. MR2712414, Show rawAMSref\bib{Klyve2007}{book}{ author={Klyve, Dominic}, title={Explicit bounds on twin primes and Brun's constant}, publisher={ProQuest LLC, Ann Arbor, MI. Thesis (Ph.D.)--Dartmouth College}, date={2007}, pages={226}, isbn={978-0549-86813-2}, review={\MR {2712414}}, } Close amsref.
[19]
H. W. Lenstra Jr. and C. Pomerance, Primality testing with Gaussian periods, J. Eur. Math. Soc. (JEMS) 21 (2019), no. 4, 1229–1269, DOI 10.4171/JEMS/861. MR3941463, Show rawAMSref\bib{Lenstra2002}{article}{ author={Lenstra, H. W., Jr.}, author={Pomerance, Carl}, title={Primality testing with Gaussian periods}, journal={J. Eur. Math. Soc. (JEMS)}, volume={21}, date={2019}, number={4}, pages={1229--1269}, issn={1435-9855}, review={\MR {3941463}}, doi={10.4171/JEMS/861}, } Close amsref.
[20]
G. Löh, Long chains of nearly doubled primes, Math. Comp. 53 (1989), no. 188, 751–759, DOI 10.2307/2008735. MR979939, Show rawAMSref\bib{Loeh89}{article}{ author={L\"{o}h, G\"{u}nter}, title={Long chains of nearly doubled primes}, journal={Math. Comp.}, volume={53}, date={1989}, number={188}, pages={751--759}, issn={0025-5718}, review={\MR {979939}}, doi={10.2307/2008735}, } Close amsref.
[21]
R. F. Lukes, C. D. Patterson, and H. C. Williams, Some results on pseudosquares, Math. Comp. 65 (1996), no. 213, 361–372, S25–S27, DOI 10.1090/S0025-5718-96-00678-3. MR1322892, Show rawAMSref\bib{LPW96}{article}{ author={Lukes, R. F.}, author={Patterson, C. D.}, author={Williams, H. C.}, title={Some results on pseudosquares}, journal={Math. Comp.}, volume={65}, date={1996}, number={213}, pages={361--372, S25--S27}, issn={0025-5718}, review={\MR {1322892}}, doi={10.1090/S0025-5718-96-00678-3}, } Close amsref.
[22]
G. L. Miller, Riemann’s hypothesis and tests for primality, J. Comput. System Sci. 13 (1976), no. 3, 300–317, DOI 10.1016/S0022-0000(76)80043-8. MR480295, Show rawAMSref\bib{Miller76}{article}{ author={Miller, Gary L.}, title={Riemann's hypothesis and tests for primality}, journal={J. Comput. System Sci.}, volume={13}, date={1976}, number={3}, pages={300--317}, issn={0022-0000}, review={\MR {480295}}, doi={10.1016/S0022-0000(76)80043-8}, } Close amsref.
[23]
T. R. Nicely, Enumeration to 10 Superscript 14 of the twin primes and Brun’s constant, Virginia J. Sci. 46 (1995), no. 3, 195–204. MR1401560, Show rawAMSref\bib{Nicely96}{article}{ author={Nicely, Thomas R.}, title={Enumeration to $10^{14}$ of the twin primes and Brun's constant}, journal={Virginia J. Sci.}, volume={46}, date={1995}, number={3}, pages={195--204}, issn={0042-658X}, review={\MR {1401560}}, } Close amsref.
[24]
C. Pomerance, On the distribution of pseudoprimes, Math. Comp. 37 (1981), no. 156, 587–593, DOI 10.2307/2007448. MR628717, Show rawAMSref\bib{Pomerance81}{article}{ author={Pomerance, Carl}, title={On the distribution of pseudoprimes}, journal={Math. Comp.}, volume={37}, date={1981}, number={156}, pages={587--593}, issn={0025-5718}, review={\MR {628717}}, doi={10.2307/2007448}, } Close amsref.
[25]
H. Riesel, Prime Numbers and Computer Methods for Factorization, 2nd ed., Progress in Mathematics, vol. 126, Birkhäuser Boston, Inc., Boston, MA, 1994. MR1292250, Show rawAMSref\bib{Riesel}{book}{ author={Riesel, Hans}, title={Prime Numbers and Computer Methods for Factorization}, series={Progress in Mathematics}, volume={126}, edition={2}, publisher={Birkh\"{a}user Boston, Inc., Boston, MA}, date={1994}, pages={xvi+464}, isbn={0-8176-3743-5}, review={\MR {1292250}}, doi={10.1007/978-1-4612-0251-6}, } Close amsref.
[26]
J. B. Rosser and L. Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64–94. MR0137689, Show rawAMSref\bib{RS62}{article}{ author={Rosser, J. Barkley}, author={Schoenfeld, Lowell}, title={Approximate formulas for some functions of prime numbers}, journal={Illinois J. Math.}, volume={6}, date={1962}, pages={64--94}, issn={0019-2082}, review={\MR {0137689}}, } Close amsref.
[27]
A. Schinzel and W. Sierpiński, Sur certaines hypothèses concernant les nombres premiers (French), Acta Arith. 4 (1958), 185–208; erratum 5 (1958), 259, DOI 10.4064/aa-4-3-185-208. MR106202, Show rawAMSref\bib{SS58}{article}{ author={Schinzel, A.}, author={Sierpi\'{n}ski, W.}, title={Sur certaines hypoth\`eses concernant les nombres premiers}, language={French}, journal={Acta Arith.}, volume={4}, date={1958}, pages={185--208; erratum \textbf {5} (1958), 259}, issn={0065-1036}, review={\MR {106202}}, doi={10.4064/aa-4-3-185-208}, } Close amsref.
[28]
J. P. Sorenson, The pseudosquares prime sieve, Algorithmic Number Theory, Lecture Notes in Comput. Sci., vol. 4076, Springer, Berlin, 2006, pp. 193–207, DOI 10.1007/11792086_15. MR2282925, Show rawAMSref\bib{Sorenson06}{article}{ author={Sorenson, Jonathan P.}, title={The pseudosquares prime sieve}, conference={ title={Algorithmic Number Theory}, }, book={ series={Lecture Notes in Comput. Sci.}, volume={4076}, publisher={Springer, Berlin}, }, date={2006}, pages={193--207}, review={\MR {2282925}}, doi={10.1007/11792086\_15}, } Close amsref.
[29]
J. P. Sorenson, Sieving for pseudosquares and pseudocubes in parallel using doubly-focused enumeration and wheel datastructures, Algorithmic Number Theory, Lecture Notes in Comput. Sci., vol. 6197, Springer, Berlin, 2010, pp. 331–339, DOI 10.1007/978-3-642-14518-6_26. MR2721430, Show rawAMSref\bib{Sorenson10a}{article}{ author={Sorenson, Jonathan P.}, title={Sieving for pseudosquares and pseudocubes in parallel using doubly-focused enumeration and wheel datastructures}, conference={ title={Algorithmic Number Theory}, }, book={ series={Lecture Notes in Comput. Sci.}, volume={6197}, publisher={Springer, Berlin}, }, date={2010}, pages={331--339}, review={\MR {2721430}}, doi={10.1007/978-3-642-14518-6\_26}, } Close amsref.
[30]
J. Sorenson and J. Webster, Strong pseudoprimes to twelve prime bases, Math. Comp. 86 (2017), no. 304, 985–1003, DOI 10.1090/mcom/3134. MR3584557, Show rawAMSref\bib{SW17}{article}{ author={Sorenson, Jonathan}, author={Webster, Jonathan}, title={Strong pseudoprimes to twelve prime bases}, journal={Math. Comp.}, volume={86}, date={2017}, number={304}, pages={985--1003}, issn={0025-5718}, review={\MR {3584557}}, doi={10.1090/mcom/3134}, } Close amsref.
[31]
K. Wooding and H. C. Williams, Doubly-focused enumeration of pseudosquares and pseudocubes, Algorithmic Number Theory, Lecture Notes in Comput. Sci., vol. 4076, Springer, Berlin, 2006, pp. 208–221, DOI 10.1007/11792086_16. MR2282926, Show rawAMSref\bib{WW2006}{article}{ author={Wooding, Kjell}, author={Williams, Hugh C.}, title={Doubly-focused enumeration of pseudosquares and pseudocubes}, conference={ title={Algorithmic Number Theory}, }, book={ series={Lecture Notes in Comput. Sci.}, volume={4076}, publisher={Springer, Berlin}, }, date={2006}, pages={208--221}, review={\MR {2282926}}, doi={10.1007/11792086\_16}, } Close amsref.
[32]
T. Z. Xuan, Integers free of small prime factors in arithmetic progressions, Nagoya Math. J. 157 (2000), 103–127, DOI 10.1017/S0027763000007212. MR1752478, Show rawAMSref\bib{Xuan2000}{article}{ author={Xuan, Ti Zuo}, title={Integers free of small prime factors in arithmetic progressions}, journal={Nagoya Math. J.}, volume={157}, date={2000}, pages={103--127}, issn={0027-7630}, review={\MR {1752478}}, doi={10.1017/S0027763000007212}, } Close amsref.
[33]
Y. Zhang, Bounded gaps between primes, Ann. of Math. (2) 179 (2014), no. 3, 1121–1174, DOI 10.4007/annals.2014.179.3.7. MR3171761, Show rawAMSref\bib{Zhang14}{article}{ author={Zhang, Yitang}, title={Bounded gaps between primes}, journal={Ann. of Math. (2)}, volume={179}, date={2014}, number={3}, pages={1121--1174}, issn={0003-486X}, review={\MR {3171761}}, doi={10.4007/annals.2014.179.3.7}, } Close amsref.

Article Information

MSC 2010
Primary: 11A41 (Primes), 11Y11 (Primality), 11Y16 (Algorithms; complexity), 68Q25 (Analysis of algorithms and problem complexity)
Author Information
Jonathan P. Sorenson
Department of Computer Science and Software Engineering, Butler University, Indianapolis, Indiana 46208
sorenson@butler.edu
MathSciNet
Jonathan Webster
Department of Mathematics, Statistics, and Actuarial Science, Butler University, Indianapolis, Indiana 46208
jewebste@butler.edu
MathSciNet
Additional Notes

A preliminary version of this work was presented as a poster at the ANTS XIII conference in Madison, Wisconsin, in July of 2018.

Journal Information
Mathematics of Computation, Volume 89, Issue 324, ISSN 0025-5718, published by the American Mathematical Society, Providence, Rhode Island.
Publication History
This article was received on , revised on , , and published on .
Copyright Information
Copyright 2020 American Mathematical Society
Article References

Settings

Change font size
Resize article panel