Size of N in primes in arithemtic progression algorithm

Question

I've been implementing the search for Primes in Arithmetic Progression (PAP) as explained by Weintraub (1976), and in his paper he refers to a number N which he sets to what seems to be an arbitrary value of 16680. Various other papers refer to N too, with no definition. Is there any math behind this, or is it just more or less guessed?

Answer 1

The number of prime arithmetic sequences of a given length that one can hope to find is determined by the chosen values of $m$ and $N$ in Weintraub's paper.

On page 241 of his paper, Weintraub says: "...it is likely that with $m = 510510$ [and $N = 16680$] there exist between 20-30 prime sequences of 16 terms..."

I was pleased to find that Weintraub's estimate of 20-30 agrees with an asymptotic formula obtained later by Grosswald (in 1982) building on a conjecture by Hardy and Littlewood. The number of q-tuples of primes $p_1$, . . . , $p_q$ in arithmetic progression, all of whose terms are less than or equal to some number $x$, was conjectured by Grosswald to be asymptotically equal to

$\frac{D_q x^2}{2(q-1)(\log x)^q}$

where $D_q$ is a factor which can be calculated relatively easily (see Theorem 1 in Grosswald, E, 1982, Arithmetic progressions that consist only of primes, J. Number Theory 14, p. 9-31).

When $q = 16$ as in Weintraub's paper, we get $D_{16} = 55651.46255350$.

Using m = 510510 and N = 16680, Weintraub said on page 241 that one gets an upper prime limit of around $8 \times 10^9$ (Weintraub actually said: "approximately $7.7 \times 10^9$").

Plugging in the numbers $q = 16$, $D_{16} = 55651.46255350$ and $x = 8 \times 10^9$ in the above formula, we get the answer 22, i.e., there are 22 prime sequences of 16 terms, in line with Weintraub's estimate of 20-30 on page 241 of his paper.

Weintraub was aware that $N = 16680$ (in conjunction with $m = 510510$) would make approximately 20-30 prime sequences of 16 terms available to his search.