A358062 -id:A358062 - cp's OEIS frontend

A003002 Size of the largest subset of the numbers [1...n] which does not contain a 3-term arithmetic progression.

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

Offset: 0

N. J. A. Sloane

"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

			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]

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.
Bloom, T. F. (2014). Quantitative results in arithmetic combinatorics (Doctoral dissertation, University of Bristol).
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.

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.
Harvey Abbott, On the Erdős-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.
Thomas F. Bloom, A quantitative improvement for Roth's theorem on arithmetic progressions, Journal of the London Mathematical Society, 93(3), 643-663 (2016).
Thomas Bloom, Problem 3, Problem 139, Problem 140, and Problem 142, Erdős Problems.
Thomas F. Bloom and Olof Sisask, Logarithmic bounds for Roth's theorem via almost-periodicity, arXiv:1810.12791 [math.CO], 2018-2019.
Thomas F. Bloom and Olof Sisask, Breaking the logarithmic barrier in Roth's theorem on arithmetic progressions, 2020 preprint. arXiv:2007.03528 [math.NT]
Thomas F. Bloom and Olof Sisask, The Kelley--Meka bounds for sets free of three-term arithmetic progressions, arXiv:2302.07211 [math.NT], 2023.
Fausto A. C. Cariboni, Sets of maximal span that yield a(n) for n = 4..209, Sep 02 2018.
Irene Choi, Shreyas Ekanathan, Aidan Gao, Tanya Khovanova, Sylvia Zia Lee, Rajarshi Mandal, Vaibhav Rastogi, Daniel Sheffield, Michael Yang, Angela Zhao, and Corey Zhao, The Struggles of Chessland, arXiv:2212.01468 [math.HO], 2022.
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).
Zander Kelley and Raghu Meka, Strong Bounds for 3-Progressions, arXiv:2302.05537 [math.NT], 2023-2024.
Zander Kelley, Strong Bounds for 3-Progressions: In-Depth, Institute for Advanced Study, YouTube video, Mar 21, 2023.
Raghu Meka, Strong Bounds for 3-Progressions, Institute for Advanced Study, YouTube video, Mar 20, 2023.
Kevin O'Bryant, Sets of Natural Numbers with Proscribed Subsets, J. Int. Seq. 18 (2015) # 15.7.7.
Quanta Magazine, 2023's Biggest Breakthroughs in Math, Three Arithmetic Progressions, YouTube video, Dec 23, 2023.
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, and X. Xu, On sets without k-term arithmetic progression, Journal of Computer and System Sciences 78 (2012) 610-618.
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: Video, Slides, Updates. (Mentions this sequence.)
Terence Tao, Erdős problem database, see nos. 3, 139-140, 142.
Samuel S. Wagstaff, Jr., On k-free sequences of integers, Math. Comp., 26 (1972), 767-771.
Wikipedia, Salem-Spencer set
Index entries related to non-averaging sequences

The classical lower bound is A104406; A229037 gives a "greedy" lower bound. - N. J. A. Sloane, Apr 29 2023
Cf. A003003, A003004, A003005, A065825, A208746, A143824.
Cf. A358062 (diagonal domination number for the n X n queen graph).
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.

(* 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 *)

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
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

Sanders proves that a(n) << n*(log log n)^5/log n. - Charles R Greathouse IV, Jan 22 2016

Bloom & Sisask prove that a(n) << n/(log n)^c for some c > 1. - Charles R Greathouse IV, Oct 11 2022

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

cp's OEIS Frontend

A003002 Size of the largest subset of the numbers [1...n] which does not contain a 3-term arithmetic progression.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A373394 Number of minimum connected dominating sets in the n X n queen graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A381091 Connected domination number of the n X n queen graph.

Views

Author

Keywords

Comments

Links

Crossrefs