A328021

Definition and sequence data

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.

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, 27, 28, 30, 29, 31, 32, 33, 35, 34, 36, 37, 38, 40, 39, 41, 42, 43, 45, 44, 46, 47, 48, 50, 49, 51, 53, 55, 52, 54, 56, 58, 60, 57, 59, 62, 65, 61, 64, 66, 63, 70, 68, 73, 67, 69, 75

Remarks

1. 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.
2. 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.
3. 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. Indeed, if x > m, we have |x - m| = x - m = x + m (mod 10) <=> 0 = 2m (mod 10) <=> m = 0 (mod 5).

Algorithm

The sequence can be computed in a greedy way as follows:

• Denote by M the set of multiples of 5 which have not yet been used.

For m in M, let N(m) be the set of possible neighbors of m, i.e., smaller numbers which did not yet occur and such that difference and sum with m do not share a digit. (It is sufficient to consider only those m for which # N(m) < 3.)

• If some N(m) is a singleton {x}, then the next two terms must be m, x.
• Otherwise, the next term is the smallest admissible number x (such that sum and difference with the preceding term do not share a digit), not used earlier, and which is not member of more than one N(m) with exactly two elements.
• Repeat.

Under the hypothesis that initially each N(m) has at least two elements, the sequence can be computed that way to an infinite length. It remains to show that each number can eventually occur, which appears to be highly probable.

PARI program

Here we provide a commented version of the PARI program, given in A328021 in condensed form.

{A_vec(n /* length of vector to compute */  /* prog A328021 v.3: dynamically increasing number of lists
      , a=1 /* initial value, not really used */
      , U=[0] /* U is the set of already used numbers, starting with U[1] = smallest unused number - 1 */
      )=
  my( c(x,y)=#setintersect(Set(digits(abs(y-x))), Set(digits(x+y))) /* count digits shared by x+y and |x-y| */
    , N(U, n=U[1]\5*5, L=List())= /* make list of neighbors for smallest multiple of 5 not in U */
        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); /* the lists L[k] will store list of neighbors of k-th next multiple of 5, including that multiple */ 
  vector(n,n, o=a; /* store current = "old" term */
    for(k=1,#L, L[k]/* if empty, pop down next ones */|| while(k<#L, L[k]=L[k+=1])||/* now in any case k=#L and we'll stop */
                if( 4 > #L[k]=N(U, if(k>1, L[k-1].last, U[1]\5*5 ))/* compute last one, if not >= elts, add a new list */,
                    L=concat(L,[N(U,L[k].last)]); print1(L.last))
    );
    for(k=1,#L, if( #L[k]<3 /* if a list has only 2 left: use the largest first */
                , c(o,a=L[k].last)&& error([n,a,o,L]) /* check (it had only 2 elements when created) */; break 
                , k==#L/* reached end of lists: Search smallest possible term */
              , a=U[1]; /* one less than smallest candidate (must be unused, admissible & not reduce 2 lists to singleton) */
                while(setsearch(U,a+=1)|| c(o,a)|| #select(L -> #L==3 && setsearch(L,a), L)>1,);
                /* if 'a' is a multiple of 5 (happens if the "neighbors" were "bad" so far), the corresponding list becomes obsolete */
                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]); /* update list of used terms */
    for(k=1,#L, setsearch(L[k],a) && L[k]=setminus(L[k],[a]));
    a)} \\ returns the vector a(1..n). WARNING: for very large n >> 10^4 one might need even more lists of neighbors.

Additional PARI code relevant for this sequence

gap(i,A=A)=abs(A[i]-A[i+1]) \\ compute gap at index i
gaps(A,m=9)=select(i->gap(i,A)>=m,[1..#A-1],1) \\ return indices of gaps >= m  /* becomes very slow for #A > 5e5.*/
fg(g=11,A=A)=for(i=2,#A,abs(A[i]-A[i-1])>g&&return(i-1)) \\ Find first gap > g /* remains very fast */
xt(i,A=A,L=9)=vecextract(A,[i-L..i+L]) \\ extract a short range around index i. Can be "applied" to a list of indices
D(A)=A[^1]-A[^-1] \\ first differences of vector A. Use, e.g., vecmax( abs( D( A )))