

A333501


The contamination sequence: a digit d must be separated from any other digit d by at least d digits different from d; this is the lexicographically earliest infinite sequence of distinct integers with this property.


1



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, 52, 70, 46, 53, 80, 47, 56, 90, 48, 57, 61, 200, 45, 62, 71, 49, 58, 63, 72, 54, 100, 64, 59, 73
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

Some integers as 11, for instance, or 22, 303, 41234, ... can never appear in this sequence.
The sequence could not go on after a term 987654321, for instance. By definition, any such term which would end the sequence is forbidden.
Terms ending in the digits 987654321, or equal to the last k < 9 digits of this (e.g., 4321) and immediately preceded by the remaining 9k digits in that order (e.g., ...98, 765), are the only possibilities preventing the sequence from going on. Indeed, if d is a nonzero digit not among the preceding d digits, then one can go on with a term of the form d*10^m for some m if there's no smaller solution. This shows that the sequence can be computed greedily, without backtracking. The second case ("equal to ...") is excluded once {1, 21, 321, 4321, ..., 87654321} = a({1, 21, 280, 2989, ...}) have appeared. One can guess that it is very unlikely that any of these 8 terms be preceded by exactly the required digits. But terms {9, 98, 987, 9876, ...} = a({9, 123, 1072, 8708, ...}, even though they are among the last ndigit terms to appear, do so roughly in their "natural position" (index ~ value), not late after the first (n+1)digit terms. So it is indeed probable that 987654321 would appear at roughly that index, and the sequence would stop there. So after 87654321, it is necessary and sufficient to exclude terms ending in 987654321 to ensure the sequence is infinite.  M. F. Hasler, Mar 31 2020
A proof (not relying on "it is probable" assertions) that attempting to greedily generate the sequence by repeatedly extending it with the smallest previouslyunused integer that satisfies the digit separation requirement, without any further checks, would at some point fail due to further extensions being blocked: consider the nine integers d000000000987654321, for d = 1 to 9. If we get to a point where none of them can extend the sequence, the sequence's last nine digits must be 987654321 and so further extensions must already be blocked. So at any point that further extensions are not blocked, it has to be possible to extend the sequence with at least one integer <= 9000000000987654321 that ends 987654321. Each time that happens, the number of integers <= 9000000000987654321 that are still available decreases. That must eventually force the sequence to be extended with an integer ending with 987654321, blocking further extensions.  David J. Seal, Apr 06 2020


LINKS

Rémy Sigrist, Table of n, a(n) for n = 1..10000
Rémy Sigrist, PARI program for A333501


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 1's);
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 non2 digits, between two 2's);
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 non2 digits between 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 2digit integer starting with 2; thus a(22) = 31, smallest term not used before that doesn't lead to an immediate contradiction.
Etc.


PROG

(PARI) See Links section.
(PARI) {A333501_vec(N=99, u=1/*least unused term*/, U=0/*bitmask of used terms > u*/, a=Vec(0, 9)/*preceding digits*/, ok(d, s=2)=!for(i=s, #d, for(k=max(id[i], 1), i1, d[k]==d[i]&&return)))= vector(N, n, while( bittest(U, 0)  !ok(digits(u)), u++; U>>=1); my(k=u); while( bittest(U, ku)  !ok(concat(a, digits(k)), 1+#a), k++); U+=1<<(ku); a=concat(a, digits(k))[9..1]; k)} \\ M. F. Hasler, Apr 01 2020


CROSSREFS

Sequence in context: A102823 A179308 A247806 * A247801 A004775 A231238
Adjacent sequences: A333498 A333499 A333500 * A333502 A333503 A333504


KEYWORD

base,nonn,changed


AUTHOR

Eric Angelini, Mar 24 2020


EXTENSIONS

Data corrected by Rémy Sigrist, Mar 25 2020
Definition and comments edited per request of the author by M. F. Hasler, Apr 01 2020


STATUS

approved



