login
Lexicographically earliest permutation of the natural numbers, such that both numbers a(n)+a(n+1) and abs(a(n)-a(n+1)) occur all in all not more than once.
4

%I #17 Jan 02 2023 12:30:51

%S 1,2,4,8,3,10,18,9,23,6,16,31,5,25,41,7,26,44,13,36,15,39,14,49,11,48,

%T 87,12,52,93,17,60,102,19,63,108,20,66,116,21,73,128,22,78,136,24,85,

%U 147,27,92,159,28,96,165,29,100,172,30,103,177,33,113,34

%N Lexicographically earliest permutation of the natural numbers, such that both numbers a(n)+a(n+1) and abs(a(n)-a(n+1)) occur all in all not more than once.

%C We want the sequence S to be a permutation of the positive integers.

%C We want S to be the lexicographically earliest sequence with these properties:

%C If we take two adjacent integers of S, say p & q, then:

%C - no other pair of adjacent integers in S has the same absolute difference |p-q|,

%C - no other pair of adjacent integers in S has the same sum (p+q),

%C - no |p-q|=(p'+q') with p'and q' being two other adjacent integers in S.

%C So S is extended with the smallest integer n such that neither |a(n-1)-a(n)|nor [a(n-1)+a(n)] has occurred before as a sum or as a difference of two adjacent integers in S.

%C A254792(n) = abs(a(n)-a(n+1));

%C A254793(n) = a(n) + a(n+1).

%H Reinhard Zumkeller, <a href="/A254788/b254788.txt">Table of n, a(n) for n = 1..10000</a>

%H Éric Angelini, <a href="http://list.seqfan.eu/oldermail/seqfan/2015-February/014392.html">Absolute diff and sums not to be shared</a>, SeqFan list, Jan 15 2015.

%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>

%e The sequence begins like this, together with their pairwise sums and absolute differences:

%e . A254793(n): 3 6 12 11 13 28 27 32 29 22 47 36 30 66 48 33 70 ...

%e . a(n): 1 2 4 8 3 10 18 9 23 6 16 31 5 25 41 7 26 44 ...

%e . A254792(n): 1 2 4 5 7 8 9 14 17 10 15 26 20 16 34 19 18 ...

%o (Haskell)

%o import Data.List (delete)

%o a254788 n = a254788_list !! (n-1)

%o a254788_list = 1 : f [2..] 1 [] where

%o f xs y zs = g xs where

%o g (w:ws) | s `elem` zs || d `elem` zs = g ws

%o | otherwise = w : f (delete w xs) w (d : s : zs)

%o where s = y + w; d = abs (y - w)

%Y Cf. A254790 (inverse), A254792, A254793.

%K nonn

%O 1,2

%A _Eric Angelini_ and _Reinhard Zumkeller_, Feb 07 2015