Problems involving arithmetic progressions

<h2 id="largest-progression-free-subsets">Largest progression-free subsets</h2>
Find the <a href="/facts/Cardinality/m6VPojwT">cardinality</a> (denoted by Ak(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, A4(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. 
In 1936, <a href="/facts/Paul_Erd%C5%91s/63LoUTe1">Paul Erdős</a> and <a href="/facts/P%C3%A1l_Tur%C3%A1n/nkWkQB6M">Pál Turán</a> posed a question related to this number<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> and Erdős set a $1000 prize for an answer to it. The prize was collected by <a href="/facts/Endre_Szemer%C3%A9di/bE2Ezgbl">Endre Szemerédi</a> for a solution published in 1975, what has become known as <a href="/facts/Szemer%C3%A9di%27s_theorem/6fjvXcEx">Szemerédi's theorem</a>.

<h2 id="arithmetic-progressions-from-prime-numbers">Arithmetic progressions from prime numbers</h2>
Main article: <a href="/facts/Primes_in_arithmetic_progression/goLLlEVE">Primes in arithmetic progression</a>
<a href="/facts/Szemer%C3%A9di%27s_theorem/6fjvXcEx">Szemerédi's theorem</a> states that a set of <a href="/facts/Natural_number/u65og8JE">natural numbers</a> of non-zero <a href="/facts/Upper_asymptotic_density/WtMTUmMJ">upper asymptotic density</a> contains finite arithmetic progressions, of any arbitrary length k.
Erdős made <a href="/facts/Erd%C5%91s_conjecture_on_arithmetic_progressions/IqSRK67D">a more general conjecture</a> from which it would follow that

The sequence of primes numbers contains arithmetic progressions of any length.
This result was proven by <a href="/facts/Ben_Green_(mathematician)/eU3YvvgM">Ben Green</a> and <a href="/facts/Terence_Tao/Do68JKn6">Terence Tao</a> in 2004 and is now known as the <a href="/facts/Green%E2%80%93Tao_theorem/kGTx52Vp">Green–Tao theorem</a>.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>
See also <a href="/facts/Dirichlet%27s_theorem_on_arithmetic_progressions/yFyJaE2d">Dirichlet's theorem on arithmetic progressions</a>.
As of 2020<a href="https://en.wikipedia.org/w/index.php?title=Problems_involving_arithmetic_progressions&action=edit">[update]</a>, the longest known arithmetic progression of primes has length 27:<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>

224584605939537911 + 81292139·23#·n, for n = 0 to 26. (<a href="/facts/Primorial/NqlQBLDp">23# = 223092870</a>)
As of 2011, the longest known arithmetic progression of consecutive primes has length 10. It was found in 1998.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a><a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> 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.

<h2 id="primes-in-arithmetic-progressions">Primes in arithmetic progressions</h2>
<a href="/facts/Prime_number_theorem/3KA9egls">The prime number theorem for arithmetic progressions</a> deals with the <a href="/facts/Asymptotic_analysis/kt87qLpu">asymptotic</a> distribution of prime numbers in an arithmetic progression.

<h2 id="covering-by-and-partitioning-into--arithmetic-progressions">Covering by and partitioning into arithmetic progressions</h2>
<ul><li>Find minimal ln such that any set of n residues modulo p can be covered by an arithmetic progression of the length ln.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a></li>
<li>For a given set S of integers find the minimal number of arithmetic progressions that cover S</li>
<li>For a given set S of integers find the minimal number of nonoverlapping arithmetic progressions that cover S</li>
<li>Find the number of ways to partition {1, ..., n} into arithmetic progressions.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a></li>
<li>Find the number of ways to partition {1, ..., n} into arithmetic progressions of length at least 2 with the same period.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a></li>
<li>See also <a href="/facts/Covering_system/sXppI4U9">Covering system</a></li></ul>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Arithmetic_combinatorics/TXKYrRWs">Arithmetic combinatorics</a></li>
<li><a href="/facts/PrimeGrid/dWDA8Scv">PrimeGrid</a></li></ul>
<h2 id="notes">Notes</h2>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Samuel S. Wagstaff, Jr. (1979). "Some Questions About Arithmetic Progressions". American Mathematical Monthly. 86 (7). Mathematical Association of America: 579–582. doi:10.2307/2320590. JSTOR 2320590. <a href="/wiki/Samuel_S._Wagstaff,_Jr." target="_blank">/wiki/Samuel_S._Wagstaff,_Jr.</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Erdős, Paul; Turán, Paul (1936). "On some sequences of integers" (PDF). Journal of the London Mathematical Society. 11 (4): 261–264. doi:10.1112/jlms/s1-11.4.261. MR 1574918. <a href="/wiki/Paul_Erd%C5%91s" target="_blank">/wiki/Paul_Erd%C5%91s</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Conlon, David; Fox, Jacob; Zhao, Yufei (2014). "The Green–Tao theorem: an exposition". EMS Surveys in Mathematical Sciences. 1 (2): 249–282. arXiv:1403.2957. doi:10.4171/EMSS/6. MR 3285854. S2CID 119301206. <a href="/wiki/David_Conlon" target="_blank">/wiki/David_Conlon</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Jens Kruse Andersen, Primes in Arithmetic Progression Records. Retrieved on 2020-08-10. <a href="http://primerecords.dk/aprecords.htm" target="_blank">http://primerecords.dk/aprecords.htm</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">H. Dubner; T. Forbes; N. Lygeros; M. Mizony; H. Nelson; P. Zimmermann, "Ten consecutive primes in arithmetic progression", Math. Comp. 71 (2002), 1323–1328. <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">the Nine and Ten Primes Project <a href="http://members.aon.at/toplicm/cp09.html" target="_blank">http://members.aon.at/toplicm/cp09.html</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Vsevolod F. Lev (2000). "Simultaneous approximations and covering by arithmetic progressions over Fp". Journal of Combinatorial Theory. Series A. 92 (2): 103–118. doi:10.1006/jcta.1999.3034. <a href="https://doi.org/10.1006%2Fjcta.1999.3034" target="_blank">https://doi.org/10.1006%2Fjcta.1999.3034</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">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. <a href="/wiki/Neil_Sloane" target="_blank">/wiki/Neil_Sloane</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">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. <a href="/wiki/Neil_Sloane" target="_blank">/wiki/Neil_Sloane</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
</ol>

Problems involving arithmetic progressions open-in-new

Problems involving arithmetic progressions