[seqfan] Re: Sum and absolute difference share no digit

[M. F. Hasler]

On Sun, Sep 29, 2019 at 8:24 AM Éric Angelini <eric.angelini at skynet.be>
wrote:

> I don't know if this sequence exists  but I'm looking for the
> lexicographically first _derangement_ of N such that the sum and the
> absolute difference of two successive terms don't share any digit.
> S = 1,2,3,5,4,6,8,10,7,9,12,11,15,14,13,...
> In computing S, one has to backtrack quite often as an  integer K
> ending with 0 or 5 cannot be followed by an integer > K.
>

Hello Eric & SeqFans,

I agree with your statement : any multiple of 5 must be sandwiched between
two smaller numbers,
because if it has a neighbor which is larger, then their sum and their
difference end in the same digit.

As often, this apparent complication finally made it even simpler:
I make a list of possible (and unused) neighbors of the "next larger
multiple of 5", and remove them if they are used in the sequence.
As soon as there is only one possible neighbor left, we simply HAVE to go
on with the multiple of 5 (we necessarily have just used its penultimate
possible neighbor) and the last remaining neighbor.
This gives the following sequence (confirming your initial terms):
[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, 72, 74, 71, 76, 78, 80,
77, 79, 81, 83, 85, 82, 84, 86, 88, 90, 87, 89, 91, 93, 95, 92, 94, 96, 98,
100, 97, 99, 102, 101, 105, 104, 103, 106, 110, 107, 111, 108, 112, 109,
115, 114, 113, 116, 120, 119, 118, 117, 121, 122, 125, 124, 123, 126, 127,
130, 129, 128, 131, 132, 135, 134, 133, 136, 137, 140, 139, 138, 141, 142,
145, 144, 143, 146, 147, 150, 149, 148, 151, 152, 153, 155, 154, 156, 160,
158, 162, 157, 159, 163, 164, 165, 161, 166, 167, 168, 170, 169, 171, 172,
173, 175, 174, 176, 177, 178, 180, 179, 181, 182, 183, 185, 184, 186, 187,
188, 190, 189, 191, 192, 193, 195, 194, 196, 197, 198, 200, 199, ...]
I include PARI code at the end of the mail. I might submit that sequence
(as co-author with Eric).

- Maximilian

PS: I had to notice that the script produces incorrect results not later
than for a(n=6784) ?=? 6781.
As this term is used, the next larger multiple of 5, 6785 has only one
other possible neighbor left, 6783, so the script produces
..., 6782, 6784, 6786, 6788, 6781, 6785, 6783 ?=? a(6786).
But here all possible neighbors of the next larger multiple of 5, 6790,
have already been used earlier, so this number could never occur, in
contradiction to the definition of the sequence.
The script should be improved to avoid that dead-end.
Is it a coincidence that this happens at n=678x, which is near 12345 / 2 ?
I actually expected that my script could stop working when the sum of
adjacent terms becomes sufficiently "pandigital":
As we reach the range where the sum of two consecutive terms is
approximately 12340, steps of 1,2 and 3 (maybe also 4) are forbidden, and
this could become a problem, at least some orders of magnitude later on,
e.g., near 123456789 / 2.
I found 5 gaps of +-9 at indices {6206, 6234, 6237, 6280, 6376}, no other
gaps larger then 8.
I did not yet try to show or disprove that the sequence could have steps >
9.
I think this would answer the question of existence of the sequence.

(PARI)
/* number of digits shared by x+y and |x-y| (0 = good) */
bad(x,y)=#setintersect(Set(digits(abs(y-x))),Set(digits(x+y)));
/* set of possible (smaller) neighbors of n (including n) */
{neighbors(n,U,L=List(n))=while(U[1]<n-=1, bad(n,L[1]) || setsearch(U,n) ||
listput(L,n)); #L>1||error(L); Vecrev(L)}
/* program for the seq.: A_vec(5000) yields the vector a(1..5000) */
A_vec(n,a=1,U=[0],N)={vector(n,n, N || N=neighbors(U[#U]\5*5+5,U);
 if( #N<3, a=N[#N], for(k=U[1]+1,oo, setsearch(U,k) || bad(a,k) || !(a=k)
|| break));
 N=setminus(N,[a]); U=setunion(U,[a]); while(#U>1&&U[2]==U[1]+1,U=U[^1]);
a)}