On the classification of Stanley sequences

An integer sequence is said to be 3-free if no three elements form an arithmetic progression. A Stanley sequence  {an}{an} is a 3-free sequence constructed by the greedy algorithm. Namely, given initial terms a0an−1an>an−1 is chosen to be the smallest such that the 3-free condition is not violated. Odlyzko and Stanley conjectured that Stanley sequences divide into two classes based on asymptotic growth: Type 1 sequences satisfy an=Θ(nlog23) and appear well-structured, while Type 2 sequences satisfy an=Θ(n2/logn) and appear disorderly. In this paper, we define the notion of regularity, which is based on local structure and implies Type 1 asymptotic growth. We conjecture that the reverse implication holds. We construct many classes of regular Stanley sequences, which include all known Type 1 sequences as special cases. We show how two regular sequences may be combined into another regular sequence, and how parts of a Stanley sequence may be translated while preserving regularity. Finally, we demonstrate the surprising fact that certain Stanley sequences possess proper subsets that are also Stanley sequences.