is a finite set of non-negative integers on which no three elements form an arithmetic progression (that is, a Salem–Spencer set), then the Stanley sequence generated from
, in sorted order, and then repeatedly chooses each successive element of the sequence to be a number that is larger than the already-chosen numbers and does not form any three-term arithmetic progression with them.
These sequences are named after Richard P. Stanley.
The Stanley sequence starting from the empty set consists of those numbers whose ternary representations have only the digits 0 and 1.
[1] That is, when written in ternary, they look like binary numbers.
Its elements are the sums of distinct powers of three, the numbers
th central binomial coefficient is 1 mod 3, and the numbers whose balanced ternary representation is the same as their ternary representation.
[2] The construction of this sequence from the ternary numbers is analogous to the construction of the Moser–de Bruijn sequence, the sequence of numbers whose base-4 representations have only the digits 0 and 1, and the construction of the Cantor set as the subset of real numbers in the interval
More generally, they are a 2-regular sequence, one of a class of integer sequences defined by a linear recurrence relation with multiplier 2.
Paul Erdős conjectured that these are the only powers of two that it contains.
[4] Andrew Odlyzko and Richard P. Stanley observed that the number of elements up to some threshold
the Stanley sequences that they considered appeared to grow more erratically but even more sparsely.
, which generates the sequence Odlyzko and Stanley conjectured that in such cases the number of elements up to any threshold
[1][5] Moy proved that Stanley sequences cannot grow significantly more slowly than the conjectured bound for the sequences of slow growth.
More precisely Moy showed that, for every such sequence, every
[6] Later authors improved the constant factor in this bound,[7] and proved that for Stanley sequences that grow as
the constant factor in their growth rates can be any rational number whose denominator is a power of three.
[8] A variation of the binary–ternary sequence (with one added to each element) was considered in 1936 by Paul Erdős and Pál Turán, who observed that it has no three-term arithmetic progression and conjectured (incorrectly) that it was the densest possible sequence with no arithmetic progression.
[9] In unpublished work with Andrew Odlyzko in 1978, Richard P. Stanley experimented with the greedy algorithm to generate progression-free sequences.
[1] Stanley sequences were named, and generalized to other starting sets than
, in a paper published in 1999 by Erdős (posthumously) with four other authors.