Sets of integers with nonlong arithmetic progressions generated by the greedy algorithm

Abstract:

Let ${S_k}$ be the set of positive integers containing no arithmetic progression of k terms, generated by the greedy algorithm. A heuristic formula, supported by computational evidence, is derived for the asymptotic density of ${S_k}$ in the case where k is composite. This formula, with a couple of additional assumptions, is shown to imply that the greedy algorithm would not maximize ${\Sigma _{n \in S}}1/n$ over all S with no arithmetic progression of k terms. Finally it is proved, without relying on any conjecture, that for all $\varepsilon > 0$, the number of elements of ${S_k}$ which are less than n is greater than $(1 - \varepsilon )\sqrt {2n}$ for sufficiently large n.