[seqfan] Re: The contamination sequence (follow up)

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

Follow up, Brussels time = 08:34

David, I think that this simple/not-so-
simple backtracking algorithm is an
old problem that was discussed many
times on the list.
My friend Jean-Marc (who has computed 
hundreds of b-files on the OEIS), once
told me that not-so-simple backtracking 
algorithm can be simple!
He has described to me a method he
has used quite often (which must be
known by programmers):
Once you have understood the
"halting" problem, you build quickly
two huge pool of integers that would 
push the sequence into a dead end:
--the first pool is made of terms that
stop  _immediately_ the seq (integers 
like 11, 112, 202, 12303 etc. which are 
the "forever banned" I mention);
-- the second pool is made of integers
"like" 9876543210.
This works fine with a lot of seqs: 
before trying to extend the seq with
the next a(n), you quickly check if
this a(n) belongs to either pool #1
or pool #2. If it doesn't, then accept
this a(n).
Forgive, as usual, my horrendous 

> 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