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
                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?

Return to MathPages Main Menu