[seqfan] Re: The lex. earliest binary cube-free sequence
David Wilson
davidwwilson at comcast.net
Tue May 2 05:11:21 CEST 2017
Mr. Gerbicz, thank you for picking up on my mistake.
It was a while ago, but I think I generated the b-file programmatically from a(0)-a(9999), and then in my inimitable style, added and incorrect a(10000) by hand.
At any rate, I wrote a new program, which verified that a(10000) was indeed the only bad element in the b-file.
Just out of curiosity, I counted the number of backtracks required to compute a(0) through a(10200), and there were only 91.
> -----Original Message-----
> From: SeqFan [mailto:seqfan-bounces at list.seqfan.eu] On Behalf Of David
> Wilson
> Sent: Monday, May 01, 2017 9:53 PM
> To: 'Sequence Fanatics Discussion list'
> Subject: [seqfan] Re: The lex. earliest binary cube-free sequence
>
> Indeed, there is a mistake.
> I will have to recompute.
> Perhaps someone else will do so as well to keep me honest.
>
> > -----Original Message-----
> > From: SeqFan [mailto:seqfan-bounces at list.seqfan.eu] On Behalf Of
> > Robert Gerbicz
> > Sent: Monday, May 01, 2017 3:37 PM
> > To: Sequence Fanatics Discussion list
> > Subject: [seqfan] Re: The lex. earliest binary cube-free sequence
> >
> > There were 10001 terms, and last one surely wrong as in the b-file
> > a(9998)=a(9999)=a(10000)=0.
> >
> > Added a quick Pari-Gp code to generate the sequence with backtracking.
> >
> > 2017-05-01 6:13 GMT+02:00 Neil Sloane <njasloane at gmail.com>:
> >
> > > Consider the set S of all (0,1}-sequences that do not contain any
> > > cubes (no substring XXX). S is non-empty since it contains
> > > Thue-Morse A010060 and also A285196. S is totally ordered by
> > > lexicographic ordering. So by the Axiom of Choice there is a minimal
> > > element.
> > >
> > > David Wilson's A282317 is defined to be this minimal element.
> > >
> > > But there is no proof, as far as I know, that the terms that he has
> > > computed are correct (although they probably are correct.) His
> > > sequence begins
> > >
> > > 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1,
> > > 0, 0, 1, ..
> > >
> > > and he gives a b-file with 10000 terms. One way that one might
> > > prove that his terms are correct would be to guess some kind of
> > > recurrence that matches his terms, and then to use this
> > > characterization to prove that the infinite extension is indeed
> > > cube-free and minimal.
> > >
> > > This is the kind of question that we all deal with every day: given
> > > a sequence, find a rule that generates it. Here is a case when it
> > > would be really nice to find a rule!
> > >
> > > Of course it could be that there is no rule, other than the definition.
> > > But that is unlikely, given that “God does not play dice with the
> > > universe”.
> > >
> > > --
> > > Seqfan Mailing list - http://list.seqfan.eu/
> > >
> >
> > --
> > Seqfan Mailing list - http://list.seqfan.eu/
>
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
More information about the SeqFan
mailing list