Note on a Computer Search for Primes in Arithmetic Progression by Weintraub (1977)

A paper by Weintraub, S, 1977 (Primes in arithmetic progression, BIT Numerical Mathematics, Vol 17, Issue 2, p. 239-243) implements a computer search for primes in arithmetic progression (PAPs). It refers to a number N which is set to what seems at first sight to be an arbitrary value of 16680. In this note I want to try to bring out some maths underlying this choice of N in Weintraub’s paper, and also record a brute force implementation I carried out in Microsoft Excel of an adjustment factor in an asymptotic formula by Grosswald (1982) which yields the number of PAPs less than or equal to some specified number.

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 the factor D_q is

\prod_{p > q} \big[\big( \frac{p}{p-1}\big)^{q-1} \cdot \frac{p - (q-1)}{p} \big] \times \prod_{p \leq q} \frac{1}{p}\big(\frac{p}{p-1}\big)^{q-1}

(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 (see below).

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 first formula above, 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 clearly aware that N = 16680 (in conjunction with m = 510510) would make approximately 20-30 prime sequences of 16 terms available to his search.

The adjustment factor of D_{16} = 55651.46255350 above can be obtained to a high degree of accuracy using a series approximation involving the zeta function (see, e.g., Caldwell, 2000, preprint, p. 11). However, I wanted to see how accurately one could calculate it by using the first one hundred thousand primes directly in Grosswald’s formula for D_q above. I did this in a Microsoft Excel sheet and got the answer D_{16} = 55651.76179. Directly using Grosswald’s formula for D_q, it was not possible to get an estimate of D_{16} accurate to the first decimal place even with one hundred thousand primes.