# [seqfan] Re: Lexicographically first 3-free sequence

franktaw at netscape.net franktaw at netscape.net
Tue Jan 21 16:11:52 CET 2014

```By the way, the graph of this sequence is awesome.

-----Original Message-----
From: franktaw <franktaw at netscape.net>
To: seqfan <seqfan at list.seqfan.eu>
Sent: Mon, Jan 20, 2014 11:37 pm
Subject: [seqfan] Re: Lexicographically first 3-free sequence

Here's a considerably better upper bound: a number m is "blocked" for
a(n) if for some
k < n/2, m = 2*a(n-k) - a(n-2k). Thus, at most floor((n-1)/2) values
can be blocked, and

a(n) <= floor((n-1)/2) + 1 = ceil(n/2).

This still doesn't seem like a particularly good bound; looking at the
data it looks like
something more like n^(2/3) as a bound.

-----Original Message-----
From: Charles Greathouse <charles.greathouse at case.edu>
To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
Sent: Mon, Jan 20, 2014 9:58 pm
Subject: [seqfan] Lexicographically first 3-free sequence

One of the JMM contest winners was Jack Grahl's A229037: Sequence of
positive integers where each is chosen to be as small as possible
subject
to the condition that no three terms a(j), a(j+k), a(j+2k) (for any j
and
k) form an arithmetic progression.

It's clear that a(n) < 2^n, since it suffices to append a number which
is
twice as large as the largest term yet appearing to avoid a 3-AP (then
use
induction). Can this trivial bound be improved? While at the JMM I had
the
opportunity to ask a Ramsey theorist, but she wasn't willing to hazard a
guess on the spot.

The only lower bound is a(n) >= 1, and I assume this cannot be improved,
that is, 1 appears infinitely often. Can this be proved?

Charles Greathouse
Analyst/Programmer
Case Western Reserve University

_______________________________________________

Seqfan Mailing list - http://list.seqfan.eu/

_______________________________________________

Seqfan Mailing list - http://list.seqfan.eu/

```