I was revisiting an old problem: Find the size of the largest subset of the numbers [1...N] which doesn't contain a 3-term arithmetic progression. I calculated the first few values and did a lookup in the sequence database: ID Number: A003002 (Formerly M0275) URL: http://www.research.att.com/projects/OEIS?Anum=A003002 Sequence: 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 Name: Number of 3-free sequences. References S. S. Wagstaff, Jr., On k-free sequences of integers, Math. Comp., 26 (1972), 767-771. Author(s): njas (My hand data goes through the first "9", at N=20. Enough terms match that I'm guessing the "Name" is not quite right.) There's a simple construction that gives a set of size 2^K for N = (3^K+1)/2. A kind of Cantor Set picture: xx_xx____xx_xx_____________xx_xx____xx_xx ... This gives sizes around N^(log2/log3), or N^.63... . I believe Erdos showed N^(1-eps) is the true answer, but haven't seen the paper. If nothing more has been done since 1972, the problem should be ripe for new computing efforts, even if no new algorithms exist. larger relevance: If we could show size < N/logN, we'd have a simple proof that primes have infinitely many 3-term APs. A harder theorem (K-term APs) was recently proved, but it was a major work. Rich