cp's OEIS Frontend

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.

%I A284516 #23 Apr 28 2017 13:00:18
%S A284516 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,
%T A284516 216,14,15,17,42,35,26,37,19,126,82,47,529,428,57,23,121,34,25,72,43,
%U A284516 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
%N 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.
%C A284516 The sequence is started with a(1) = 1 and always extended with the smallest integer not yet present and not leading to a contradiction.
%C A284516 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
%C A284516 It can be conjectured that any number which is not an intrinsically impossible term will eventually appear.
%C A284516 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
%H A284516 Lars Blomberg, <a href="/A284516/b284516.txt">Table of n, a(n) for n = 1..10001</a>
%e A284516 The first eleven terms are [1,2,13,24,5,3,6,7,4,8,52].
%e A284516 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.
%e A284516 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.
%e A284516 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.
%e A284516 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.
%e A284516 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.
%e A284516 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.
%e A284516 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.
%o A284516 (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
%K A284516 nonn,base
%O A284516 1,2
%A A284516 _Eric Angelini_ and _Lars Blomberg_, Mar 28 2017