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

Return to MathPages Main Menu