|
%I M0275 #137 Jan 21 2024 10:57:05
%S 0,1,2,2,3,4,4,4,4,5,5,6,6,7,8,8,8,8,8,8,9,9,9,9,10,10,11,11,11,11,12,
%T 12,13,13,13,13,14,14,14,14,15,16,16,16,16,16,16,16,16,16,16,17,17,17,
%U 18,18,18,18,19,19,19,19,19,20,20,20,20,20,20,20,20,21,21,21,22,22,22,22
%N Size of the largest subset of the numbers [1...n] which does not contain a 3-term arithmetic progression.
%C "Sequences containing no 3-term arithmetic progressions" is another phrase people may be searching for.
%C a(n) = size of largest subset of [1..n] such that no term is the average of any two others. These are also called non-averaging sets, or 3-free sequences. - _N. J. A. Sloane_, Mar 01 2012
%C More terms of this sequence can be found directly from A065825, because A003002(n) (this sequence) = the integer k such that A065825(k) <= n < A065825(k+1). - _Shreevatsa R_, Oct 18 2009
%D H. L. Abbott, On a conjecture of Erdos and Straus on non-averaging sets of integers, Proc. 5th British Combinatorial Conference, 1975, pp. 1-4.
%D Bloom, T. F. (2014). Quantitative results in arithmetic combinatorics (Doctoral dissertation, University of Bristol).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D E. G. Straus, Nonaveraging sets. In Combinatorics (Proc. Sympos. Pure Math., Vol. XIX, Univ. California, Los Angeles, Calif., 1968), pp. 215-222. Amer. Math. Soc., Providence, R.I., 1971. MR0316255 (47 #4803)
%D T. Tao and V. Vu, Additive Combinatorics, Problem 10.1.3.
%H Fausto A. C. Cariboni, <a href="/A003002/b003002.txt">Table of n, a(n) for n = 0..211</a>
%H Harvey Abbott, <a href="http://dx.doi.org/10.2140/pjm.1980.91.1">Extremal problems on nonaveraging and nondividing sets</a>, Pacific Journal of Mathematics 91.1 (1980): 1-12.
%H Harvey Abbott, <a href="https://doi.org/10.1007/BF01949131">On the Erdős-Straus non-averaging set problem</a>, Acta Mathematica Hungarica 47.1-2 (1986): 117-119.
%H Tanbir Ahmed, Janusz Dybizbanski and Hunter Snevily, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i4p29">Unique Sequences Containing No k-Term Arithmetic Progressions</a>, Electronic Journal of Combinatorics, 20(4), 2013, #P29.
%H F. Behrend, <a href="http://www.pnas.org/content/32/12/331.full.pdf">On sets of integers which contain no three terms in an arithmetic progression</a>, Proc. Nat. Acad. Sci. USA, v. 32, 1946, pp. 331-332. MR0018694.
%H Thomas F. Bloom, <a href="https://research-information.bris.ac.uk/ws/portalfiles/portal/70486994/paperfinite_simplediss.pdf">A quantitative improvement for Roth's theorem on arithmetic progressions</a>, Journal of the London Mathematical Society, 93(3), 643-663 (2016).
%H Thomas F. Bloom and Olof Sisask, <a href="https://arxiv.org/abs/1810.12791">Logarithmic bounds for Roth's theorem via almost-periodicity</a>, arXiv:1810.12791 [math.CO], 2018-2019.
%H Thomas F. Bloom and Olof Sisask, <a href="https://arxiv.org/abs/2007.03528">Breaking the logarithmic barrier in Roth's theorem on arithmetic progressions</a>, 2020 preprint. arXiv:2007.03528 [math.NT]
%H Thomas F. Bloom and Olof Sisask, <a href="https://arxiv.org/abs/2302.07211">The Kelley--Meka bounds for sets free of three-term arithmetic progressions</a>, arXiv:2302.07211 [math.NT], 2023.
%H Fausto A. C. Cariboni, <a href="/A003002/a003002.txt">Sets of maximal span that yield a(n) for n = 4..209</a>, Sep 02 2018.
%H Irene Choi, Shreyas Ekanathan, Aidan Gao, Tanya Khovanova, Sylvia Zia Lee, Rajarshi Mandal, Vaibhav Rastogi, Daniel Sheffield, Michael Yang, Angela Zhao, and Corey Zhao, <a href="https://arxiv.org/abs/2212.01468">The Struggles of Chessland</a>, arXiv:2212.01468 [math.HO], 2022.
%H Janusz Dybizbanski, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i2p15">Sequences containing no 3-term arithmetic progressions</a>, Electronic Journal of Combinatorics, 19(2), 2012, #P15. [Gives first 120 terms].
%H P. Erdõs and E. G. Straus, <a href="https://users.renyi.hu/~p_erdos/1970-05.pdf">Nonaveraging sets II</a>, In Combinatorial theory and its applications, II (Proc. Colloq., Balatonfüred, 1969), pp. 405-411. North-Holland, Amsterdam, 1970. MR0316256 (47 #4804).
%H Zander Kelley and Raghu Meka, <a href="https://arxiv.org/abs/2302.05537">Strong Bounds for 3-Progressions</a>, arXiv:2302.05537 [math.NT], 2023-2024.
%H Zander Kelley, <a href="https://www.youtube.com/watch?v=v2nDGjldXUE">Strong Bounds for 3-Progressions: In-Depth</a>, Institute for Advanced Study, YouTube video, Mar 21, 2023.
%H Raghu Meka, <a href="https://www.youtube.com/watch?v=ExU5NZsLDcU">Strong Bounds for 3-Progressions</a>, Institute for Advanced Study, YouTube video, Mar 20, 2023.
%H K. O'Bryant, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/OBryant/obr3.html">Sets of Natural Numbers with Proscribed Subsets</a>, J. Int. Seq. 18 (2015) # 15.7.7
%H Quanta Magazine, <a href="https://youtu.be/4HHUGnHcDQw?t=861">2023's Biggest Breakthroughs in Math</a>, Three Arithmetic Progressions, YouTube video, Dec 23, 2023.
%H Karl C. Rubin, <a href="/A003002/a003002.pdf">On sequences of integers with no k terms in arithmetic progression</a>, 1973 [Scanned copy, with correspondence]
%H Tom Sanders, <a href="http://arxiv.org/abs/1011.0104">On Roth's theorem on progressions</a>, arXiv:1011.0104 [math.CA], 2010-2011; Annals of Mathematics 174:1 (2011), pp. 619-636.
%H Z. Shao, F. Deng, M. Liang, and X. Xu, <a href="http://dx.doi.org/10.1016/j.jcss.2011.09.003">On sets without k-term arithmetic progression</a>, Journal of Computer and System Sciences 78 (2012) 610-618.
%H N. J. A. Sloane, New Gilbreath Conjectures, Sum and Erase, Dissecting Polygons, and Other New Sequences, Doron Zeilberger's Exper. Math. Seminar, Rutgers, Sep 14 2023: <a href="https://vimeo.com/866583736?share=copy">Video</a>, <a href="http://neilsloane.com/doc/EMSep2023.pdf">Slides</a>, <a href="http://neilsloane.com/doc/EMSep2023.Updates.txt">Updates</a>. (Mentions this sequence.)
%H Samuel S. Wagstaff, Jr., <a href="http://dx.doi.org/10.1090/S0025-5718-1972-0325500-5">On k-free sequences of integers</a>, Math. Comp., 26 (1972), 767-771.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Salem-Spencer_set">Salem-Spencer set</a>
%H <a href="/index/No#non_averaging">Index entries related to non-averaging sequences</a>
%F Sanders proves that a(n) << n*(log log n)^5/log n. - _Charles R Greathouse IV_, Jan 22 2016
%F Bloom & Sisask prove that a(n) << n/(log n)^c for some c > 1. - _Charles R Greathouse IV_, Oct 11 2022
%e Examples from Dybizbanski (2012) (includes earlier examples found by other people):
%e n, a(n), example of an optimal subset:
%e 0, 0, []
%e 1, 1, [1]
%e 2, 2, [1, 2]
%e 4, 3, [1, 2, 4]
%e 5, 4, [1, 2, 4, 5]
%e 9, 5, [1, 2, 4, 8, 9]
%e 11, 6, [1, 2, 4, 5, 10, 11]
%e 13, 7, [1, 2, 4, 5, 10, 11, 13]
%e 14, 8, [1, 2, 4, 5, 10, 11, 13, 14]
%e 20, 9, [1, 2, 6, 7, 9, 14, 15, 18, 20]
%e 24, 10, [1, 2, 5, 7, 11, 16, 18, 19, 23, 24]
%e 26, 11, [1, 2, 5, 7, 11, 16, 18, 19, 23, 24, 26]
%e 30, 12, [1, 3, 4, 8, 9, 11, 20, 22, 23, 27, 28, 30]
%e 32, 13, [1, 2, 4, 8, 9, 11, 19, 22, 23, 26, 28, 31, 32]
%e 36, 14, [1, 2, 4, 8, 9, 13, 21, 23, 26, 27, 30, 32, 35, 36]
%e 40, 15, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 32, 37, 38, 40]
%e 41, 16, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 32, 37, 38, 40, 41]
%e 51, 17, [1, 2, 4, 5, 10, 13, 14, 17, 31, 35, 37, 38, 40, 46, 47, 50, 51]
%e 54, 18, [1, 2, 5, 6, 12, 14, 15, 17, 21, 31, 38, 39, 42, 43, 49, 51, 52, 54]
%e 58, 19, [1, 2, 5, 6, 12, 14, 15, 17, 21, 31, 38, 39, 42, 43, 49, 51, 52, 54, 58]
%e 63, 20, [1, 2, 5, 7, 11, 16, 18, 19, 24, 26, 38, 39, 42, 44, 48, 53, 55, 56, 61, 63]
%e 71, 21, [1, 2, 5, 7, 10, 17, 20, 22, 26, 31, 41, 46, 48, 49, 53, 54, 63, 64, 68, 69, 71]
%e 74, 22, [1, 2, 7, 9, 10, 14, 20, 22, 23, 25, 29, 46, 50, 52, 53, 55, 61, 65, 66, 68, 73, 74]
%e 82, 23, [1, 2, 4, 8, 9, 11, 19, 22, 23, 26, 28, 31, 49, 57, 59, 62, 63, 66, 68, 71, 78, 81, 82]
%t (* Program not suitable to compute a large number of terms *)
%t a[n_] := a[n] = For[r = Range[n]; k = n, k >= 1, k--, If[AnyTrue[Subsets[r, {k}], FreeQ[#, {___, a_, ___, b_, ___, c_, ___} /; b - a == c - b] &], Return[k]]];
%t Table[Print["a(", n, ") = ", a[n]]; a[n], {n, 1, 25}] (* _Jean-François Alcover_, Jan 21 2018 *)
%o (PARI) ap3(v)=for(i=1,#v-2, for(j=i+2,#v, my(t=v[i]+v[j]); if(t%2==0 && setsearch(v,t/2), return(1)))); 0
%o a(N)=forstep(n=N,2,-1, forvec(v=vector(n,i,[1,N]),if(!ap3(v), return(n)),2)); N \\ _Charles R Greathouse IV_, Apr 22 2022
%Y The classical lower bound is A104406; A229037 gives a "greedy" lower bound. - _N. J. A. Sloane_, Apr 29 2023
%Y Cf. A003003, A003004, A003005, A065825, A208746, A143824.
%Y A selection of sequences related to "no three-term arithmetic progression": A003002, A003003, A003278, A004793, A005047, A005487, A033157, A065825, A092482, A093678, A093679, A093680, A093681, A093682, A094870, A101884, A101886, A101888, A140577, A185256, A208746, A229037.
%K nonn,nice
%O 0,3
%A _N. J. A. Sloane_
%E Extended from 53 terms to 80 terms, using a simple brute-force program with some pruning, by _Shreevatsa R_, Oct 18 2009
%E See Dybizbanski (2012) for first 120 terms. - _N. J. A. Sloane_, Dec 17 2013
%E Edited by _N. J. A. Sloane_, Apr 12 2016
%E a(0)=0 prepended by _Alois P. Heinz_, May 14 2020
|
