A284516 Lexicographically earliest sequence of unique numbers such that for each digit "d" the gap to the nearest other digit "d" is equal to d.

1, 2, 13, 24, 5, 3, 6, 7, 4, 8, 52, 9, 62, 73, 18, 131, 91, 21, 32, 41, 31, 54, 16, 12, 51, 216, 14, 15, 17, 42, 35, 26, 37, 19, 126, 82, 47, 529, 428, 57, 23, 121, 34, 25, 72, 43, 65, 83, 74, 96, 53, 48, 235, 29, 36, 27, 325, 86, 39, 75, 300, 81, 61, 92, 45, 261, 415, 28, 324, 63, 59, 482, 652, 141, 93, 64, 231, 2161, 38, 49

Offset: 1

Author

Eric Angelini and Lars Blomberg, Mar 28 2017

Keywords

• nonn
• base

Comments

The sequence is started with a(1) = 1 and always extended with the smallest integer not yet present and not leading to a contradiction.

The rule excludes substrings with two digits d not separated by d other digits (like "11", "22", ... or "212", "232", ...) and also isolated "0"s (i.e., surrounded by nonzero digits, like in "101", "102", ...). Numbers having such substrings within their digits can never occur. This explains empty horizontal bands in the graph, in particular between 11*10^k and 12*10^k. - M. F. Hasler, Mar 28 2017

It can be conjectured that any number which is not an intrinsically impossible term will eventually appear.

Define the "greedy algorithm" to be the algorithm that computes this sequence by choosing the next term as the smallest integer that does not lead to an immediate contradiction to the rules, including the requirements produced by the term itself. In particular, the term may not contain two digits which would each require the respective digit to occur for a second time at the same later position. (E.g., the number 43, if there is no '3' or '4' within the preceding 5 digits, would require both a '3' and a '4' to follow after 3 other digits.) Then this greedy algorithm would block itself by choosing a(353) = 456, preceded by ...,719, 164, 2372, 4391, 817. There is no immediate contradiction, but it would imply that the following digits must be x,y,4,8,5,z,6. However, there is no possible choice for x. Another choice would be a(353) = 635, making it also impossible to continue. If these two values are forbidden at that point, the algorithm will make the correct choice of a(353) = 1000, and continue with no further problem beyond n = 1000. - M. F. Hasler, Apr 28 2017

Examples

			The first eleven terms are [1,2,13,24,5,3,6,7,4,8,52].
The gap between the digit "1" of the first term (1) and the digit "1" of the third term (13) is exactly of 1 digit (the "2" of the second term) and no other gap is smaller than 1 digit.
The gap between the digit "2" of the second term (2) and the digit "2" of the fourth term (24) is exactly of 2 digits (the digits 1 and 3 of the third term) and no other gap is smaller than 2 digits.
The gap between the digit "1" of the third term (13) and the digit "1" of the first term (1) is exactly of 1 digit (the digit "2" of the second term), and no other gap is smaller than 1 digit.
The gap between the digit "3" of the third term (13) and the digit "3" of the sixth term (3) is exactly of 3 digits (the digits 2, 4 and 5 of the fourth and fifth terms) and no other gap is smaller than 3 digits.
The gap between the digit "2" of the fourth term (24) and the digit "2" of the second term (2) is exactly of 2 digits (the digits 1 and 3 of the third term) and no other gap is smaller than 2 digits.
The gap between the digit "4" of the fourth term (24) and the digit "4" of the ninth term (4) is exactly of 4 digits (the digits 5, 3, 6 and 7 of the fifth to the eighth terms) and no other gap is smaller than 4 digits.
The gap between the digit "5" of the fifth term (5) and the digit "5" of the last term (52) is exactly of 5 digits (the digits 3, 6, 7, 4 and 8 of the sixth to the tenth terms) and no other gap is smaller than 5 digits.
		

Links

• Lars Blomberg, Table of n, a(n) for n = 1..10001

Programs

PARI

A284516(N,show=1,F=[456,635],U=[0],a=vector(20))={my(ok(d,r=vector(10))=!forstep(i=#d,11^(#d>20),-1,(i>20||#d<20) && for(j=max(i-d[i],1),i-1,d[j]==d[i] && return); (i-d[i]<2 || d[i-d[i]-1]==d[i]) && next; i+d[i]<#d && (d[i+d[i]+1]==d[i] && next || return); (r[i+d[i]-#d+1] || !r[i+d[i]-#d+1]=d[i])&&return)); for(n=1,N, my(k=U[1]); until(!setsearch(U,k++) && (k>N || ok(digits(k)) || !U=setunion(U,[k])) && ok(concat(a,digits(k))) && (!F || k!=F[1] || 0*F=F[^1]),); show&&printf("%d,",if(show>1,[n,k],k)); a=concat(a,digits(k))[-20..-1]; U=setunion(U,[k]); U[2]<=U[1]+1 && U=U[^1]); k} \\ If k is the smallest as yet unused number, we check whether it is "impossible" on its own, and in this case consider it as an already-used (= forbidden) number, stored in the set U (having as smallest member the least unused value - 1). Doing this for any k would result in a large set U and be less efficient. - M. F. Hasler, Apr 04 2017, updated Apr 28 2017