login
Size of the largest subset of the numbers [1...n] which doesn't contain a 4-term arithmetic progression.
(Formerly M0439)
12

%I M0439 #64 Apr 13 2022 13:25:16

%S 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 17,17,18,18,18,19,20,20,20,21,21,21,22,22,22,23,23,24,24,24,25,25,26,

%U 26,26,27,28,28,28,28,29,29,30,30,30,30,31,31,32,32,33,33,34,34,34

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

%C These subsets have been called 4-free sequences.

%C 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 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 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Fausto A. C. Cariboni, <a href="/A003003/b003003.txt">Table of n, a(n) for n = 1..142</a>

%H Fausto A. C. Cariboni, <a href="/A003003/a003003_1.txt">Sets that yield a(n) for n = 5..142</a>, Jun 15 2018

%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 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 Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992

%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 Z. Shao, F. Deng, M. Liang, 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 S. 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 Cf. A003002, A003004, A003005, A065825, A136746.

%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

%O 1,2

%A _N. J. A. Sloane_

%E a(52)-a(72) from _Rob Pratt_, Jul 09 2015