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

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, 17, 17, 18, 18, 18, 19, 20, 20, 20, 21, 21, 21, 22, 22, 22, 23, 23, 24, 24, 24, 25, 25, 26, 26, 26, 27, 28, 28, 28, 28, 29, 29, 30, 30, 30, 30, 31, 31, 32, 32, 33, 33, 34, 34, 34

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• changed

Comments

These subsets have been called 4-free sequences.

Szemeredi's theorem for arithmetic progressions of length 4 asserts that a(n) is o(n) as n -> infinity. - Doron Zeilberger, Mar 26 2008

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

References

• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Fausto A. C. Cariboni, Table of n, a(n) for n = 1..142
• Thomas Bloom, Problem 3, Problem 139, and Problem 142, Erdős Problems.
• Fausto A. C. Cariboni, Sets that yield a(n) for n = 5..142, Jun 15 2018
• Kevin O'Bryant, Sets of Natural Numbers with Proscribed Subsets, J. Int. Seq. 18 (2015) # 15.7.7
• Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
• Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
• Karl C. Rubin, On sequences of integers with no k terms in arithmetic progression, 1973 [Scanned copy, with correspondence]
• Zehui Shao, Fei Deng, Meilian Liang, and Xiaodong Xu, On sets without k-term arithmetic progression, Journal of Computer and System Sciences 78 (2012) 610-618.
• Terence Tao, Erdős problem database, see nos. 3, 139, 142.
• Samuel S. Wagstaff, Jr., On k-free sequences of integers, Math. Comp., 26 (1972), 767-771.

Crossrefs

Cf. A003002, A003004, A003005, A065825, A136746.

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.

Extensions

a(52)-a(72) from Rob Pratt, Jul 09 2015