[seqfan] Re: Lexicographically first 3-free sequence

[franktaw at netscape.net]

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

Franklin T. Adams-Watters

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

Franklin T. Adams-Watters

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