[seqfan] Re: The contamination sequence

[M. F. Hasler]

Eric, David et al,

In case this sequence is finite, one can certainly consider the *different*
sequence which *by definition* is infinite.
(which is equivalent to forbid terms that can't have an immediate
successor, see below).
Concerning the sequence as it is currently defined:
A term *ending in* the digits 987654321, or a term *equal to* the last k
digits of this, e.g., 4321, immediately preceded by the remaining 9-k
digits in that order (e.g., ...98, 765), is the only possibility which
would prevent the sequence from going on.
(Proof: If d is a nonzero digit missing among the preceding d digits, then
one can always go on with a term of the form d*10^m for some m if there's
no smaller solution.)
The *second *case ("equal to") is excluded once 1, 21, 321, ..., 987654321
have appeared.
Infinitely many numbers satisfy the *first *condition ("ending in"), but it
is not obvious whether such a number can ever occur.
I would not be surprised that one could show this isn't the case.
(Think about it: What is the condition for a term to end in 987654321? In
particular, what can be its predecessors and the "leading digits" of that
term?)

Maximilian

On Tue, Mar 31, 2020, 02:27 Éric Angelini <eric.angelini at skynet.be> wrote:

> 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)
> cents.
> É.
>
>
>
> > 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,...
> >>>
> >>> EXAMPLE:
> >>> 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.
> >>>
>
>