cp's OEIS Frontend

A003003 Size of the largest subset of the numbers [1...n] which doesn't contain a 4-term arithmetic progression.

%I A003003 M0439 #70 Sep 03 2025 15:13:11
%S A003003 1,2,3,3,4,5,5,6,7,8,8,8,9,9,10,10,11,11,12,12,13,13,14,14,15,15,16,
%T A003003 17,17,18,18,18,19,20,20,20,21,21,21,22,22,22,23,23,24,24,24,25,25,26,
%U A003003 26,26,27,28,28,28,28,29,29,30,30,30,30,31,31,32,32,33,33,34,34,34
%N A003003 Size of the largest subset of the numbers [1...n] which doesn't contain a 4-term arithmetic progression.
%C A003003 These subsets have been called 4-free sequences.
%C A003003 Szemeredi's theorem for arithmetic progressions of length 4 asserts that a(n) is o(n) as n -> infinity. - _Doron Zeilberger_, Mar 26 2008
%C A003003 False g.f. (z^12 + 1 - z^11 - z^10 + z^8 - z^6 + z^5 - z^3 + z)/((z+1)*(z-1)^2) was conjectured by _Simon Plouffe_ in his 1992 dissertation, but in fact is wrong (cf. A136746).
%D A003003 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A003003 Fausto A. C. Cariboni, <a href="/A003003/b003003.txt">Table of n, a(n) for n = 1..142</a>
%H A003003 Thomas Bloom, <a href="https://www.erdosproblems.com/3">Problem 3</a>, <a href="https://www.erdosproblems.com/139">Problem 139</a>, and <a href="https://www.erdosproblems.com/142">Problem 142</a>, Erdős Problems.
%H A003003 Fausto A. C. Cariboni, <a href="/A003003/a003003_1.txt">Sets that yield a(n) for n = 5..142</a>, Jun 15 2018
%H A003003 Kevin 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 A003003 Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H A003003 Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992
%H A003003 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 A003003 Zehui Shao, Fei Deng, Meilian Liang, and Xiaodong 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 A003003 Terence Tao, <a href="https://github.com/teorth/erdosproblems/blob/main/README.md#table">Erdős problem database</a>, see nos. 3, 139, 142.
%H A003003 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.
%Y A003003 Cf. A003002, A003004, A003005, A065825, A136746.
%Y A003003 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 A003003 nonn,changed
%O A003003 1,2
%A A003003 _N. J. A. Sloane_
%E A003003 a(52)-a(72) from _Rob Pratt_, Jul 09 2015