The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A003002 Size of the largest subset of the numbers [1...n] which does not contain a 3-term arithmetic progression. (Formerly M0275) 29
 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, 12, 13, 13, 13, 13, 14, 14, 14, 14, 15, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 18, 18, 18, 18, 19, 19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 20, 20, 21, 21, 21, 22, 22, 22, 22 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,3 COMMENTS "Sequences containing no 3-term arithmetic progressions" is another phrase people may be searching for. 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 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] REFERENCES 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. N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence). 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) T. Tao and V. Vu, Additive Combinatorics, Problem 10.1.3. LINKS Fausto A. C. Cariboni, Table of n, a(n) for n = 0..211 Harvey Abbott, Extremal problems on nonaveraging and nondividing sets, Pacific Journal of Mathematics 91.1 (1980): 1-12. H. Abbott, On the Erdos-Straus non-averaging set problem, Acta Mathematica Hungarica 47.1-2 (1986): 117-119. Tanbir Ahmed, Janusz Dybizbanski and Hunter Snevily, Unique Sequences Containing No k-Term Arithmetic Progressions, Electronic Journal of Combinatorics, 20(4), 2013, #P29. F. Behrend, On sets of integers which contain no three terms in an arithmetic progression, Proc. Nat. Acad. Sci. USA, v. 32, 1946, pp. 331-332. MR0018694. Fausto A. C. Cariboni, Sets of maximal span that yield a(n) for n = 4..209, Sep 02 2018. Janusz Dybizbanski, Sequences containing no 3-term arithmetic progressions, Electronic Journal of Combinatorics, 19(2), 2012, #P15. [Gives first 120 terms]. P. Erdõs and E. G. Straus, Nonaveraging sets II, In Combinatorial theory and its applications, II (Proc. Colloq., Balatonfüred, 1969), pp. 405-411. North-Holland, Amsterdam, 1970. MR0316256 (47 #4804). K. O'Bryant, Sets of Natural Numbers with Proscribed Subsets, J. Int. Seq. 18 (2015) # 15.7.7 Karl C. Rubin, On sequences of integers with no k terms in arithmetic progression, 1973 [Scanned copy, with correspondence] Tom Sanders, On Roth's theorem on progressions, arXiv:1011.0104 [math.CA], 2010-2011; Annals of Mathematics 174:1 (2011), pp. 619-636. Z. Shao, F. Deng, M. Liang, X. Xu, On sets without k-term arithmetic progression, Journal of Computer and System Sciences 78 (2012) 610-618. Samuel S. Wagstaff, Jr., On k-free sequences of integers, Math. Comp., 26 (1972), 767-771. Wikipedia, Salem-Spencer set FORMULA Sanders proves that a(n) << n*(log log n)^5/log n. - Charles R Greathouse IV, Jan 22 2016 EXAMPLE Examples from Dybizbanski (2012) (includes earlier examples found by other people): n, a(n), example of an optimal subset: 0, 0, [] 1, 1, [1] 2, 2, [1, 2] 4, 3, [1, 2, 4] 5, 4, [1, 2, 4, 5] 9, 5, [1, 2, 4, 8, 9] 11, 6, [1, 2, 4, 5, 10, 11] 13, 7, [1, 2, 4, 5, 10, 11, 13] 14, 8, [1, 2, 4, 5, 10, 11, 13, 14] 20, 9, [1, 2, 6, 7, 9, 14, 15, 18, 20] 24, 10, [1, 2, 5, 7, 11, 16, 18, 19, 23, 24] 26, 11, [1, 2, 5, 7, 11, 16, 18, 19, 23, 24, 26] 30, 12, [1, 3, 4, 8, 9, 11, 20, 22, 23, 27, 28, 30] 32, 13, [1, 2, 4, 8, 9, 11, 19, 22, 23, 26, 28, 31, 32] 36, 14, [1, 2, 4, 8, 9, 13, 21, 23, 26, 27, 30, 32, 35, 36] 40, 15, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 32, 37, 38, 40] 41, 16, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 32, 37, 38, 40, 41] 51, 17, [1, 2, 4, 5, 10, 13, 14, 17, 31, 35, 37, 38, 40, 46, 47, 50, 51] 54, 18, [1, 2, 5, 6, 12, 14, 15, 17, 21, 31, 38, 39, 42, 43, 49, 51, 52, 54] 58, 19, [1, 2, 5, 6, 12, 14, 15, 17, 21, 31, 38, 39, 42, 43, 49, 51, 52, 54, 58] 63, 20, [1, 2, 5, 7, 11, 16, 18, 19, 24, 26, 38, 39, 42, 44, 48, 53, 55, 56, 61, 63] 71, 21, [1, 2, 5, 7, 10, 17, 20, 22, 26, 31, 41, 46, 48, 49, 53, 54, 63, 64, 68, 69, 71] 74, 22, [1, 2, 7, 9, 10, 14, 20, 22, 23, 25, 29, 46, 50, 52, 53, 55, 61, 65, 66, 68, 73, 74] 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] MATHEMATICA (* Program not suitable to compute a large number of terms *) 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]]]; Table[Print["a(", n, ") = ", a[n]]; a[n], {n, 1, 25}] (* Jean-François Alcover, Jan 21 2018 *) CROSSREFS Cf. A003003, A003004, A003005, A065825, A208746, A143824. Sequence in context: A297995 A081228 A270826 * A087180 A029121 A161205 Adjacent sequences:  A002999 A003000 A003001 * A003003 A003004 A003005 KEYWORD nonn,nice AUTHOR EXTENSIONS Extended from 53 terms to 80 terms, using a simple brute-force program with some pruning, by Shreevatsa R, Oct 18 2009 See Dybizbanski (2012) for first 120 terms. - N. J. A. Sloane, Dec 17 2013 Edited by N. J. A. Sloane, Apr 12 2016 a(0)=0 prepended by Alois P. Heinz, May 14 2020 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified May 14 04:12 EDT 2021. Contains 343872 sequences. (Running on oeis4.)