info prev up next book cdrom email home

Prime Arithmetic Progression

Let the number of Primes of the form $mk+n$ less than $x$ be denoted $\pi_{m,n}(x)$. Then

\lim_{x\to\infty} {\pi_{a,b}(x)\over \mathop{\rm Li}\nolimits (x)} = {1\over\phi(a)},

where $\mathop{\rm Li}\nolimits (x)$ is the Logarithmic Integral and $\phi(x)$ is the Totient Function.

Let $P$ be an increasing arithmetic progression of $n$ Primes with minimal difference $d > 0$. If a Prime $p\leq n$ does not divide $d$, then the elements of $P$ must assume all residues modulo $p$, specifically, some element of $P$ must be divisible by $p$. Whereas $P$ contains only primes, this element must be equal to $p$.

If $d < n\char93 $ (where $n\char93 $ is the Primorial of $n$), then some prime $p\leq n$ does not divide $d$, and that prime $p$ is in $P$. Thus, in order to determine if $P$ has $d < n\char93 $, we need only check a finite number of possible $P$ (those with $d < n\char93 $ and containing prime $p\leq n$) to see if they contain only primes. If not, then $d\geq n\char93 $. If $d = n\char93 $, then the elements of $P$ cannot be made to cover all residues of any prime $p$. The Prime Patterns Conjecture then asserts that there are infinitely many arithmetic progressions of primes with difference $d$.

A computation shows that the smallest possible common difference for a set of $n$ or more Primes in arithmetic progression for $n=1$, 2, 3, ... is 0, 1, 2, 6, 6, 30, 150, 210, 210, 210, 2310, 2310, 30030, 30030, 30030, 510510, ... (Sloane's A033188, Ribenboim 1989, Dubner and Nelson 1997, Wilson). The values up to $n=13$ are rigorous, while the remainder are lower bounds which assume the validity of the Prime Patterns Conjecture and are simply given by $p_{n-7}\char93 $, where $p_i$ is the $i$th Prime. The smallest first terms of arithmetic progressions of $n$ primes with minimal differences are 2, 2, 3, 5, 5, 7, 7, 199, 199, 199, 60858179, 147692845283, 14933623, ... (Sloane's A033189; Wilson).

Smaller first terms are possible for nonminimal $n$-term progressions. Examples include the 8-term progression $11+1210230k$ for $k=0$, 1, ..., 7, the 12-term progression $23143+30030k$ for $k=0$, 1, ..., 11 (Golubev 1969, Guy 1994), and the 13-term arithmetic progression $766439+510510k$ for $k=0$, 1, ..., 12 (Guy 1994).

The largest known set of primes in Arithmetic Sequence is 22,


for $k=0$, 1, ..., 21 (Pritchard et al. 1995, UTS School of Mathematical Sciences).

The largest known sequence of consecutive Primes in Arithmetic Progression (i.e., all the numbers between the first and last term in the progression, except for the members themselves, are composite) is ten, given by
for $k=0$, 1, ..., 9, discovered by Harvey Dubner, Tony Forbes, Manfred Toplic, et al. on March 2, 1998. This beats the record of nine set on January 15, 1998 by the same investigators,
for $k=0$, 1, ..., 8 (two sequences of nine are now known), the progression of eight consecutive primes given by
for $k=0$, 1, ..., 7, discovered by Harvey Dubner, Tony Forbes, et al. on November 7, 1997 (several are now known), and the progression of seven given by
$ 1,089,533,431,247,059,310,875,780,378,922,957,732,$
$ 908,036,492,993,138,195,385,213,105,561,742,150,$
$ 447,308,967,213,141,717,486,151+210k,$
for $k=0$, 1, ..., 6, discovered by H. Dubner and H. K. Nelson on Aug. 29, 1995 (Peterson 1995, Dubner and Nelson 1997). The smallest sequence of six consecutive Primes in arithmetic progression is


for $k=0$, 1, ..., 5 (Lander and Parkin 1967, Dubner and Nelson 1997). According to Dubner et al., a trillion-fold increase in computer speed is needed before the search for a sequence of 11 consecutive primes is practical, so they expect the ten-primes record to stand for a long time to come.

It is conjectured that there are arbitrarily long sequences of Primes in Arithmetic Progression (Guy 1994).

See also Arithmetic Progression, Cunningham Chain, Dirichlet's Theorem, Linnik's Theorem, Prime Constellation, Prime-Generating Polynomial, Prime Number Theorem, Prime Patterns Conjecture, Prime Quadruplet


Abel, U. and Siebert, H. ``Sequences with Large Numbers of Prime Values.'' Amer. Math. Monthly 100, 167-169, 1993.

Caldwell, C. K. ``Cunningham Chain.''

Courant, R. and Robbins, H. ``Primes in Arithmetical Progressions.'' §1.2b in Supplement to Ch. 1 in What is Mathematics?: An Elementary Approach to Ideas and Methods, 2nd ed. Oxford, England: Oxford University Press, pp. 26-27, 1996.

Davenport, H. ``Primes in Arithmetic Progression'' and ``Primes in Arithmetic Progression: The General Modulus.'' Chs. 1 and 4 in Multiplicative Number Theory, 2nd ed. New York: Springer-Verlag, pp. 1-11 and 27-34, 1980.

Dubner, H. and Nelson, H. ``Seven Consecutive Primes in Arithmetic Progression.'' Math. Comput. 66, 1743-1749, 1997.

Forbes, T. ``Searching for 9 Consecutive Primes in Arithmetic Progression.''

Forman, R. ``Sequences with Many Primes.'' Amer. Math. Monthly 99, 548-557, 1992.

Golubev, V. A. ``Faktorisation der Zahlen der Form $x^3\pm 4x^2+3x\pm 1$.'' Anz. Österreich. Akad. Wiss. Math.-Naturwiss. Kl. 184-191, 1969.

Guy, R. K. ``Arithmetic Progressions of Primes'' and ``Consecutive Primes in A.P.'' §A5 and A6 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 15-17 and 18, 1994.

Lander, L. J. and Parkin, T. R. ``Consecutive Primes in Arithmetic Progression.'' Math. Comput. 21, 489, 1967.

Madachy, J. S. Madachy's Mathematical Recreations. New York: Dover, pp. 154-155, 1979.

Nelson, H. L. ``There Is a Better Sequence.'' J. Recr. Math. 8, 39-43, 1975.

Peterson, I. ``Progressing to a Set of Consecutive Primes.'' Sci. News 148, 167, Sep. 9, 1995.

Pritchard, P. A.; Moran, A.; and Thyssen, A. ``Twenty-Two Primes in Arithmetic Progression.'' Math. Comput. 64, 1337-1339, 1995.

Ramaré, O. and Rumely, R. ``Primes in Arithmetic Progressions.'' Math. Comput. 65, 397-425, 1996.

Ribenboim, P. The Book of Prime Number Records, 2nd ed. New York: Springer-Verlag, p. 224, 1989.

Shanks, D. ``Primes in Some Arithmetic Progressions and a General Divisibility Theorem.'' §104 in Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, pp. 104-109, 1993.

Sloane, N. J. A. A033188 and A033189 in ``An On-Line Version of the Encyclopedia of Integer Sequences.''

Weintraub, S. ``Consecutive Primes in Arithmetic Progression.'' J. Recr. Math. 25, 169-171, 1993.

Zimmerman, P.

info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein