|
| |
|
|
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 9-k 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 n-digit 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 previously-unused 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
|
|
|
|
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 non-2 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 non-2 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 2-digit 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(i-d[i], 1), i-1, d[k]==d[i]&&return)))= vector(N, n, while( bittest(U, 0) || !ok(digits(u)), u++; U>>=1); my(k=u); while( bittest(U, k-u) || !ok(concat(a, digits(k)), 1+#a), k++); U+=1<<(k-u); a=concat(a, digits(k))[-9..-1]; k)} \\ M. F. Hasler, Apr 01 2020
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
base,nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
Definition and comments edited per request of the author by M. F. Hasler, Apr 01 2020
|
|
|
STATUS
|
approved
|
| |
|
|
