[seqfan] Re: The contamination sequence

Éric Angelini eric.angelini at skynet.be
Mon Mar 30 08:06:59 CEST 2020

Brussels, 08:05 local time
Hello David,
yes, I guess you pointed the problem 
in the right way: for me 11 and 9876543210
are not exactly the same type of number (here).
11 is immediately forbidden.
9876543210 is not.
A greedy algorithm will discard 11
because 11 embeds a contradiction;
the same algorithm will accept
9876543210 and the seq will stop.
This is not exactly the same (for me).
Backtracking is not needed with 11.
You say it is with 9876543210.
But the aims are different in this case.
Without backtracking the seq stops
at some point (I guess -- this is 
precisely the conjecture).
With a "simple" backtracking it might 
grow forever.
But are we sure that a simple backtracking 
would then be enough?
Will we not need a not-so-simple
backtracking to go on when the
simple backtracking extends the
seq for, say, 10000 terms then leads
the seq into a dead end?
I would appreciate a deep investigation 
about the fate of the sequence _without_ any backtracking at all
(simple or smart). If, like the "Automatic Ant",
the seq turns into a process tout
describe (extension with 10, 1010,
101010, etc.) I would jump of joy!
My two (socially distant, uncontaminated)

> Le 30 mars 2020 à 04:28, David Seal <david.j.seal at gwynmop.com> a écrit :
> I don't see how the following conjecture in the (now non-draft) A333501 sequence can be correct:
> "The sequence is conjectured to be finite as no term can come after 987654321, for instance. But the sequence could halt much earlier."
> In particular, there are infinite sequences of distinct positive integers with the given property, such as 10, 1010, 101010, 10101010, ..., so the only question is whether a lexicographically earliest such infinite sequence exists. If it does, it's infinite (by definition); if it doesn't, it's non-existent; it's not finite in either case!
> You describe a simple process for generating the lexicographically earliest infinite sequence with a particular property: try appending further terms to the sequence, starting with the smallest positive integer which hasn't yet been used and working upwards through other such integers, until you find one that doesn't lead to an immediate contradiction. It's an inadequate process because contradictions might not be immediate: it's possible that at some point 987654321 is the smallest positive integer that doesn't produce an immediate contradiction in the same way that 11 does, but it does produce a contradiction as soon as you try to append another integer, whatever that integer is. That contradiction means that 987654321 is just as 'forever banned' as 11 is, just for a less immediate reason.
> To deal with that, your process needs to be extended to deal with non-immediate contradictions like that. It could do that by backtracking when it finds itself in a 'dead end' such as the one produced by 987654321 - i.e. having found itself unable to extend the sequence further, go back a step to the selection of 987654321, effectively saying "no, 987654321 wasn't a valid choice after all, so try the next lowest integer". It will eventually find one, because if 987654321 didn't lead to an immediate contradiction, it's certain that 9876543210 won't either, and 9876543210 can be followed by any positive integer that hasn't yet been used. So something bigger than 987654321 will avoid the problem with 987654321 itself - either 9876543210 or something smaller.
> Once one knows that infinite sequences with a given property do exist, as we do in this case, we know that such a backtracking process won't run into a contradiction that proves the sequence is finite. The reason that the lexicographically earliest infinite sequence with the property might not exist is not that you might run into such a contradiction, but that the process of avoiding all the contradictions ends up giving you a sequence without the property. For example, a purported sequence definition "the lexicographically earliest sequence of distinct positive integers that doesn't include at least one positive integer" would run into that problem: it's nonexistent because if it defined a sequence and that sequence didn't contain N, then 1, 2, 3, 4, ..., N-1, N, N+2, N+3, N+4, N+5, ... would be a lexicographically earlier such sequence. The backtracking process will generate first 1, then 2, then 3, then 4, etc, never being forced to backtrack because there is always a sequence starting 1, 2, 3, 4, ..., N that subsequently fails to include at least one positive integer - and so it generates A000027, which includes every positive integer.
> It seems to me that A333501 won't run into such an issue, because its property is a 'local' one that depends on at most its last 10 terms, not a 'global' one that depends on all the terms so far. If every partial sequence fixed upon by the backtracking process has the property that digits d are separated by at least d non-d digits, so does the infinite sequence it generates, and we know that once the backtracking process has produced at least ten digits beyond the current point that it has reached, it won't backtrack past that point and so has fixed on the partial sequence it generates up to that point.
> In fact, I think that the sequence can be generated in a non-backtracking way, provided we look one digit ahead of the digits that will be appended by the candidate integer we're considering appending to it. Specifically, rather than just checking that the current candidate N doesn't breach the "digits d separated by at least d non-d digits" property, it should check each of nine possibilities for the property: N followed by a 1 at the start of the following term, N followed by a 2 at the start of the the following term, etc, up to N followed by a 9 at the start of the following term. If all of those possibilities breach the property (as in the case N = 987654321), reject N and try the next candidate term to be appended; if at least one of those possibilities doesn't breach the property, accept N because we know that the sequences with the property can be continued infinitely after appending N. (Proof: if appending N followed by a nonzero digit d doesn't breach the property, neither does appending N followed by further terms that produce the digits sequence d0d0d0d0..., and we can always produce such further terms by spacing the commas sufficiently far apart. The result of doing so won't be the lexicographically smallest infinite continuation of the sequence with N appended, but it will be a legitimate infinite continuation with N appended and so establishes that backtracking from a decision to append N won't be needed.)
> David
>> On 29 March 2020 at 12:36 Éric Angelini <eric.angelini at skynet.be> wrote:
>> Case closed, sorry -- Rémy has checked 
>> and corrected the seq in the meantime.
>> à+
>> É.
>> Catapulté de mon aPhone
>>> Le 25 mars 2020 à 18:05, Éric Angelini <bk263401 at skynet.be> a écrit :
>>> Hello SeqFans,
>>> I think some issues here might be interesting:
>>> (copy/paste from the draft < https://oeis.org/draft/A333501) >)
>>> I would appreciate if someone could compute 10000 terms or so:
>>> I would like to see the graph and be sure that the sequence 
>>> doesn't stop before the 10000th term.
>>> Thank you in advance,
>>> Best,
>>> É.
>>> -------------------------------------------------------------
>>> The contamination sequence: a digit d must be separated at least by d non-d digits from any other digit d; this is the lexicographically earliest sequence of distinct integers with this property.
>>> 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 30, 21, 31, 24, 32, 50, 23, 40, 25, 34, 26, 35, 27, 38, 29, 36, 41, 37, 28, 39, 42, 51, 60, 43,...
>>> a(18) = 19 and a(19) = 20; what could come next?
>>> Not a(20) = 11 (the smallest unused term in the sequence) because 11 is forever banned (at least one digit, which is not 1, must separate the two 1s);
>>> not a(20) = 21 as there is only one digit between the 2 of 20 and the 2 of 21 (the digits' succession would be 202 and we want at least two non-2 digits, between two 2s);
>>> not a(20) = 22 (of course), nor 23, 24, ... 29 as all those integers start with 2;
>>> a(20) = 30 is ok.
>>> What comes next? Not a(21) = 11, of course, but a(21) = 21 is ok, as there are more than 2 non-2 digits beween the 2 of 20 and the 2 of 21 (the digits' succession here is 20302, which is ok);
>>> What next? Not a(22) = 11 or 22 (banned forever) and not a 2-digit integer starting with 2; thus a(22) = 31, smallest term not used before that doesn't lead to an immediate contradiction. Etc.
>>> -----------------------------------------
>>> --
>>> 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