**Problems involving arithmetic progressions** are of interest in number theory,^{[1]} combinatorics, and computer science, both from theoretical and applied points of view.

## Largest progression-free subsets

Find the cardinality (denoted by *A*_{k}(*m*)) of the largest subset of {1, 2, ..., *m*} which contains no progression of *k* distinct terms. The elements of the forbidden progressions are not required to be consecutive.

For example, *A*_{4}(10) = 8, because {1, 2, 3, 5, 6, 8, 9, 10} has no arithmetic progressions of length 4, while all 9-element subsets of {1, 2, ..., 10} have one. Paul Erdős set a $1000 prize for a question related to this number, collected by Endre Szemerédi for what has become known as Szemerédi's theorem.

## Arithmetic progressions from prime numbers

Szemerédi's theorem states that a set of natural numbers of non-zero upper asymptotic density contains finite arithmetic progressions, of any arbitrary length *k*.

Erdős made a more general conjecture from which it would follow that

*The sequence of primes numbers contains arithmetic progressions of any length.*

This result was proven by Ben Green and Terence Tao in 2004 and is now known as the Green–Tao theorem.^{[2]}

See also Dirichlet's theorem on arithmetic progressions.

As of 2020^{[update]}, the longest known arithmetic progression of primes has length 27:^{[3]}

- 224584605939537911 + 81292139·23#·
*n*, for*n*= 0 to 26. (23# = 223092870)

As of 2011, the longest known arithmetic progression of *consecutive* primes has length 10. It was found in 1998.^{[4]}^{[5]} The progression starts with a 93-digit number

- 100 99697 24697 14247 63778 66555 87969 84032 95093 24689
- 19004 18036 03417 75890 43417 03348 88215 90672 29719

and has the common difference 210.

Source about Erdős-Turán Conjecture of 1936:

- P. Erdős and P. Turán, On some sequences of integers, J. London Math. Soc. 11 (1936), 261–264.

## Primes in arithmetic progressions

The prime number theorem for arithmetic progressions deals with the asymptotic distribution of prime numbers in an arithmetic progression.

## Covering by and partitioning into arithmetic progressions

- Find minimal
*l*such that any set of_{n}*n*residues modulo*p*can be covered by an arithmetic progression of the length*l*._{n}^{[6]} - For a given set
*S*of integers find the minimal number of arithmetic progressions that cover*S* - For a given set
*S*of integers find the minimal number of nonoverlapping arithmetic progressions that cover*S* - Find the number of ways to partition {1, ...,
*n*} into arithmetic progressions.^{[7]} - Find the number of ways to partition {1, ...,
*n*} into arithmetic progressions of length at least 2 with the same period.^{[8]} - See also Covering system

## See also

## Notes

**^**Samuel S. Wagstaff, Jr. (1979). "Some Questions About Arithmetic Progressions".*American Mathematical Monthly*. Mathematical Association of America.**86**(7): 579–582. doi:10.2307/2320590. JSTOR 2320590.**^**Weisstein, Eric W. "Prime Arithmetic Progression".*MathWorld*.**^**Jens Kruse Andersen,*Primes in Arithmetic Progression Records*. Retrieved on 2020-08-10.**^**H. Dubner; T. Forbes; N. Lygeros; M. Mizony; H. Nelson; P. Zimmermann, "Ten consecutive primes in arithmetic progression", Math. Comp. 71 (2002), 1323–1328.**^**the Nine and Ten Primes Project**^**Vsevolod F. Lev (2000). "Simultaneous approximations and covering by arithmetic progressions over F_{p}".*Journal of Combinatorial Theory, Series A*.**92**(2): 103–118. doi:10.1006/jcta.1999.3034.**^**Sloane, N. J. A. (ed.). "Sequence A053732 (Number of ways to partition {1,...,n} into arithmetic progressions of length >= 1)".*The On-Line Encyclopedia of Integer Sequences*. OEIS Foundation.**^**Sloane, N. J. A. (ed.). "Sequence A072255 (Number of ways to partition {1,2,...,n} into arithmetic progressions...)".*The On-Line Encyclopedia of Integer Sequences*. OEIS Foundation.