## Sequences With No Arithmetic Progressions

```Let s(n) denote the nth term of an integer sequence such that s(0)=0
and s(k) for all k>0 is the least natural number such that no four
elements of {s(0),..,s(k)} are in arithmetic progression.  For example,
s(1178)=11218 and s(2352)=30006.  What is the asymptotic density of
the sequence s(n)?

I might seem that s(n) increases as roughly n^4/3, but Rob Harley
computed a further data point s(27200) = 999991, which doesn't match
very well with the value 27200^(4/3) ~= 818010.  Our three data points
are
n             ln(s(n))/ln(n)
------          -------------
1178             1.3186
2351             1.3280
27200             1.3530

I wonder if the ratio of logs converges on some finite value as
n -> oo.  I think the sum of 1/s(n) (n=1 to oo) converges, but
I haven't evaluated the sum.

Rob Harley looked at the corresponding sequence for 3-term progressions
and found jumps of factors of two at powers of two, e.g., s(2047)=88573
and s(2048)=177147.  This is consistent with Richard Guy's description
of sequences with no m-term progressions:

"If m is a power of three, or twice a power of three, then the
members of the sequence are fairly easy to describe in terms of
their ternary expansions, but for other values the sequences
behave quite erratically.  Their rates of growth seem similar,
but this has yet to be proved."

It's interesting to note that the sequence s(n) contains many sets of
three consecutive integers.  The first member of every such set less
than 30000 is listed below

0   7   14   28   48   55   64   86   108   168
286  371  471  633  760  982  1032  1136  1261  1600
1739  1788  1822  1848  3832  4225  5504  7729  8062
9229  10110  21977  27953

Are there infinitely many sets of three consecutive integers in the
sequence s(n)?  Rob Harley checked up to a million, and found

0 7 14 28 48 55... [snip]... 773304 822652 822765 877853 894199

So there are still triplets up that far but they appear to get
progressively less more rare.  Presumably there are infinitely many
such triples.  Can anyone supply a proof?
```