Paper detail

On the growth of Stanley sequences

A set is said to be \emph{3-free} if no three elements form an arithmetic progression. Given a 3-free set $A$ of integers $0=a_0<a_1<\cdots<a_t$, the \emph{Stanley sequence} $S(A)=\{a_n\}$ is defined using the greedy algorithm: For each successive $n>t$, we pick the smallest possible $a_n$ so that $\{a_0,a_1,\ldots,a_n\}$ is 3-free and increasing. Work by Odlyzko and Stanley indicates that Stanley sequences may be divided into two classes. Sequences of Type 1 are highly structured and satisfy $αn^{\log_2 3}/2\le a_n\le αn^{\log_2 3}$, for some constant $α$, while those of Type 2 are chaotic and satisfy $Θ(n^2/\log n)$. In this paper, we consider the possible values for $α$ in the growth of Type 1 Stanley sequences. Whereas Odlyzko and Stanley assumed $α=1$, we show that $α$ can be any rational number which is at least 1 and for which the denominator, in lowest terms, is a power of 3.