login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

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 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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 27 21:52 EDT 2020. Contains 334671 sequences. (Running on oeis4.)