[seqfan] Re: More about lex earliest cubefree 0,1 sequence
Neil Sloane
njasloane at gmail.com
Mon May 22 02:38:20 CEST 2017
Maximilian, I see you already updated A282317
with information that you have certified the first 130 terms.
Now that the sequence has a proper start, and is no longer purely
conjectural, I think the b-file should be changed into an
a-file, and labeled as a conjectured continuation out
to 10000 terms. Unless someone wants to extend Maximilian's work, and
certify more terms of the 10000?
Best regards
Neil
Neil J. A. Sloane, President, OEIS Foundation.
11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
Phone: 732 828 6098; home page: http://NeilSloane.com
Email: njasloane at gmail.com
On Sun, May 21, 2017 at 7:44 PM, Neil Sloane <njasloane at gmail.com> wrote:
> Maximilian: excellent - will you please update the sequence
> with a comment about what you did?
>
> By the way, you said
> > To cover the case where XXX would start later in WT, re-do the
> previous lines with W truncated by some of its first digit(s).
> That is exactly why, in my previous email, I said to consider
> an arbitrary subword P of the sequence.
>
>
> Best regards
> Neil
>
> Neil J. A. Sloane, President, OEIS Foundation.
> 11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
> Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
> Phone: 732 828 6098 <(732)%20828-6098>; home page: http://NeilSloane.com
> Email: njasloane at gmail.com
>
>
> On Sun, May 21, 2017 at 4:18 PM, M. F. Hasler <seqfan at hasler.fr> wrote:
>
>> On Sat, May 20, 2017 at 5:47 PM, Neil Sloane wrote:
>> > Dear Seqfans,
>> > I claim that the first 6 terms are correct, because the sequence S =
>> 0010T
>> > = 001001101001... = PT is cubefree(...)
>> > The starting point is the fact (Allouche and Shallit, Automatic Seqs.,
>> pp.
>> > 14-15) that T is not only cubefree, it is overlap-free, meaning there
>> is no
>> > substring of the form ABABA, where B is a binary string and A is 0 or 1.
>>
>> Indeed, this generalizes to an initial segment W of S of arbitrary length:
>> Suppose WT = XXX... with length(X) > length(W), specifically X=WY.
>> Then T=YXX... = YWYWY... = ABABA... with AB = YW, length(A)=1:
>> T not overlap free, contradiction.
>>
>> To cover the case where XXX would start later in WT, re-do the
>> previous lines with W truncated by some of its first digit(s).
>>
>> So it appears to me that the "such-and-such property" you mentioned
>> earlier is:
>> "WT does not start with a cube XXX with length(X) <= length(W),
>> and the same for any left-truncation of W."
>>
>> That way we can prove (quite easily) that arbitrarily long initial
>> segments W of S are correct (because they can be extended to an
>> infinite cubefree sequence).
>> (Of course not all initial segments will work, e.g., if W ends in
>> ...00 then WT does contain a cube. We need to find a suitable W
>> containing at least the segment we want to prove correct.)
>>
>> I have done this for the displayed 130 terms. (To do so it is
>> sufficient to check that the concatenation of these 130 terms with the
>> initial 260 initial terms of the Thue-Morse sequence A010060 is
>> cubefree, which happens to be the case.)
>>
>> - Maximilian
>>
>> --
>> Seqfan Mailing list - http://list.seqfan.eu/
>>
>
>
More information about the SeqFan
mailing list