cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

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

Original entry on oeis.org

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

Views

Author

N. J. A. Sloane

Keywords

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

Examples

			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]

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

Links

Crossrefs

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.

Programs

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

Formula

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

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

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.