A328021 - OEIS

%I #36 Oct 04 2019 22:05:41

%S 1,2,3,5,4,6,8,10,7,9,12,11,15,14,13,16,17,18,20,19,21,22,23,25,24,26,

%T 27,28,30,29,31,32,33,35,34,36,37,38,40,39,41,42,43,45,44,46,47,48,50,

%U 49,51,53,55,52,54,56,58,60,57,59,62,65,61,64,66,63,70,68,73,67,69,75

%N Lexicographic first permutation of {1,...,N} such that a(n) + a(n+1) and |a(n) - a(n+1)| never share a digit, with N as large as possible.

%C Any multiple of 5 must occur between two strictly smaller terms, since the sum and the difference with a larger term would share the final digit, cf. example.

%C It is not yet known whether N can be arbitrarily large. We know that N >= 10^5. If N may be arbitrarily large, it is understood that this sequence is the limiting sequence as N -> oo, which is then a permutation of the positive integers.

%C The sequence could be of finite length N and the corresponding permutation of all positive integers could exist nonetheless. It would then have max{a(k), k <= n} > n for all n > N.

%C When a term is near x = 123456789*10^k / 2, its neighbor x + d must be such that x + (x + d) = 2x + d = 123456789*10^k + d is not pandigital and does not share any digit with d, i.e., d > 10^k or d < -10^k/9. This shows that the "jumps" become arbitrarily large, in case N can be arbitrarily large (and in particular, if we could have such a permutation of all positive integers).

%C The first gap |a(n) - a(n+1)| of size 1, 2, ..., 11 occurs at n = (1, 3, 8, 12, 68, 69, 66, 676, 6206, 17261, 11715). The next larger gap is one of 30 at n = 62492, then a gap of 33 at n = 512492, and a gap of 50 at n = 617442. These n yield 2n = 124984, 1024984 resp. 1234884: close to records for number of distinct digits.

%C The sequence can be computed in a greedy way by updating a list of possible neighbors for the multiples of 5. Whenever such a list has only one element left, we must use that multiple of 5 followed by its only remaining possible neighbor.

%C In case two or more lists would shrink to a singleton at the same time (cf example about a(6888) = 6891), this term must be forbidden.

%e After the initial (1, 2, 3), we must not use 4, because otherwise 5 would have at least one neighbor > 5, but then their sum and difference will have the same final digit, since x + 5 = x - 5 (mod 10).

%e Therefore, the sequence must continue (5, 4, 6).

%e Now we cannot use 7 which would yield a sum of 6 + 7 = 13, sharing a digit with |6 - 7| = 1. Therefore, a(7) = 8.

%e Indeed, no step of +-1 may occur as long as the sum has leading digit '1' (also later when consecutive terms are in the range 50 .. 100), therefore 7 and 9 are excluded, but a(8) = 10 is possible, and (7, 9) thereafter.

%e Then, 11 is excluded since the step of 11 - 9 = 2 would share a digit with the sum 9 + 11 = 20, but 12 is possible, etc.

%e Considering only one list (of possible neighbors of the next multiple of 5) would lead to a dead end after a(6784) = 6788: here the smallest yet unused multiple of 5, 6785, has still two possible neighbors, 6781 and 6783. One might want to use 6781 after 6788 (which would then require 6785 and 6783). But 6790 (next larger multiple of 5) has only 6781 as possible neighbor left, once 6788 is used. Therefore, one must use a(6785) = 6790 immediately after 6788 and before a(6786) = 6781, in order to be able to go on with a(6787) = 6785, a(6788) = 6783, and further.

%e A similar situation happens at a(6867) = 6869 which must be followed by 6875, while 6870 comes later.

%e After a(6888) = 6891, the smallest possible term would be 6886. However, this is the penultimate of both, possible neighbors of 6890 (6886 and 6888) and of 6895 (6886 and 6893). The smallest possibility which does not lead to a dead end is a(6889) = 6893, followed by 6895, 6886, 6890, 6888.

%o (PARI) A328021_vec(n,a=1,U=[0])={my(c(x,y)=#setintersect(Set(digits(abs(y-x))), Set(digits(x+y))), N(U,n=U[1]\5*5, L=List())=while(setsearch(U,n+=5),); listput(L,n); while(U[1]<n-=1, c(n,L[1])||setsearch(U,n)||listput(L,n)); Vecrev(L), L.last=L[#L], L=[[]],o); vector(n,n,o=a; for(k=1,#L, L[k]|| while(k<#L, L[k]=L[k+=1])|| if(4>#L[k]=N(U, if(k>1,L[k-1].last,U[1]\5*5)), L=concat(L,[N(U,L[k].last)]))); for(k=1,#L, if(#L[k]<3, c(o,a=L[k].last)&& error([n,a,o,L]); break, k==#L, a=U[1]; while(setsearch(U,a+=1)|| c(o,a)|| #select(L->#L==3&&setsearch(L,a),L)>1,); a%5||for(k=1,#L,a==L[k].last&& L[k]=[]))); U=setunion(U,[a]); while(#U>1&&U[2]==U[1]+1, U=U[^1]); for(k=1,#L, L[k]=setminus(L[k],[a]));a)} \\ Returns the vector a(1..n). See oeis.org/wiki/A328021 for well formatted & commented version. Computation takes only a few seconds for n = 666 666, but several minutes for n = 700 000.

%K nonn,base

%O 1,2

%A _Eric Angelini_ and _M. F. Hasler_, Oct 01 2019