[seqfan] Re: More about lex earliest cubefree 0,1 sequence
Neil Sloane
njasloane at gmail.com
Sun May 21 02:04:50 CEST 2017
MFH, let me expand my last reply.
You said:
(quote):
We also know that A282317 is "minimal": by construction (I refer to the
computed terms) it is the lexicographically smallest cubefree sequence that
can be constructed in a precise greedy way guaranteeing minimality, which
does not seem to require backtracking:
Essentially, append at each step the largest possible part of the existing
sequence; if a cube would appear then "increase" it (in the sense of a
binary word) at the point where the earliest cube would end and discard the
rest, until it's cubefree.
If this never results in a maximal cubefree word (A282133), then it is
infinite and also correct (since minimal and cubefree by construction).
So it would also be sufficient to show that the words constructed in that
way (S.S'.1 where S' is the longest possible truncation of S so that S.S'.1
is cubefree) are never maximal.
(end quote)
In particular, where you say:
We also know that A282317 is "minimal": by construction (I refer to the
computed terms),
I disagree. By its definition the sequence A282317 is minimal, yes. But we
do not know that the 10000 terms proposed by David Wilson are correct. It
is possible that there is no way to extend them to an infinite cubefree
sequence. Your algorithm also produced the same terms, which is a good sign.
But I don't think you have a proof that your algorithm works. At least,
that's what you said
when we discussed this around May 6.
This is also why I am unhappy about including sequences that are derived on
the assumption that the conjectured
terms for A282317 are correct. (Such as A286940)
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 Sat, May 20, 2017 at 7:55 PM, Neil Sloane <njasloane at gmail.com> wrote:
> Maximilian, I thought that there was no proof that your algorithm works.
>
> (We had an email discussion about this)
>
> 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 Sat, May 20, 2017 at 7:13 PM, M. F. Hasler <seqfan at hasler.fr> wrote:
>
>> On Sun, May 21, 2017 at 12:02 AM, Antti Karttunen <
>> antti.karttunen at gmail.com
>> > wrote:
>>
>> > Dear M. F. Hasler,
>> > in the algorithm you describe in http://oeis.org/A282317 ?
>> > That is, how much shorter (than the previous total length of S) each new
>> > added segment W is at each "approximate doubling" step?
>>
>> Is there any regularity to this sequence?
>> >
>>
>> Antti,
>> thanks for your interest in this.
>> Yes, indeed there is a pseudo-regularity:
>> I have just submitted https://oeis.org/draft/A286940 with the length of
>> the
>> words appended at the n-th step (a(0...2) being somehow arbitrary).
>>
>> The sequence starts
>>
>> 1, 1, 1, 3, 2, 7, 15, 13,
>>
>> 1, 42, 39, 42, 39, 42, 28,
>>
>> 1, 42, 39, 42, 39, 42, 28,
>>
>> 1, 42, 39, 42, 39, 35, 7, 32, 7, 35, 7, 32, 7, 35, 7, 32, 4,
>>
>> 39, 42, 39, 42, 39, 35, 7, 32, 7, 35, 7, 32, 7, 35, 7, 32, 4,
>>
>> 39, 42, 39, 42, 39, 35, 7, 32, 7, 35, 7, 32, 7, 35, 7, 32, 4, 28,
>>
>> 1, 42, 39, 42, 39, 42, 28,
>>
>> 1, 42, 39, 42, 39, 42, 28,
>>
>> 1, 42, 39, 42, 39, 35, 7, 32, 7, 35, 7, 32, 7, 35, 7, 32, 4,
>>
>> 39, 42, 39, 42, 39, 35, 7, 32, 7, 35, ...
>>
>> --
>> Maximilian
>>
>> --
>> Seqfan Mailing list - http://list.seqfan.eu/
>>
>
>
More information about the SeqFan
mailing list