cp's OEIS Frontend

A363708 Lexicographically earliest sequence of positive integers such that the n-th pair of consecutive equal values are separated by a(n) terms, with pairs numbered according to the position of the first term in the pair.

%I A363708 #29 Jun 29 2023 13:21:14
%S A363708 1,2,1,3,2,3,4,5,2,4,6,5,7,2,5,4,8,7,9,10,2,4,10,11,8,12,2,10,13,14,
%T A363708 15,13,11,12,14,16,2,17,10,2,18,15,12,13,19,20,21,14,17,22,23,17,10,
%U A363708 24,2,13,12,15,20,12,25,21,17,26,14,27,28,22,29,30,31,32
%N A363708 Lexicographically earliest sequence of positive integers such that the n-th pair of consecutive equal values are separated by a(n) terms, with pairs numbered according to the position of the first term in the pair.
%C A363708 Calculating terms may require backtracking, since pair numbers are not fixed until enough later terms either do or don't pair with earlier terms.
%H A363708 Pontus von Brömssen, <a href="/A363708/b363708.txt">Table of n, a(n) for n = 1..200</a>
%e A363708 The first pair (1,2,1) encloses 1 term because a(1)=1.
%e A363708 The second pair (2,1,3,2) encloses 2 terms because a(2)=2.
%e A363708 The third pair (3,2,3) encloses 1 term because a(3)=1.
%e A363708 The fourth pair (2,3,4,5,2) encloses 3 terms because a(4)=3.
%e A363708 In constructing the sequence, we must consider whether a number forms a pair with some earlier term, and if so, whether this leads to a contradiction. If every existing term leads to a contradiction, then the smallest number not yet in the sequence is used, as in a(7)=4.
%e A363708 a(7)=4 because if a(7)=1, we get (1,2,1,3,2,3,1). This would have the third pair in the sequence enclose 3 terms even though a(3)=1, which is satisfied by the pair (3,2,3).
%e A363708 If a(7)=2: (1,2,1,3,2,3,2) would have the fourth pair (2,3,2) enclose 1 term, which is impossible because a(4)=3 means the fourth pair encloses 3 terms.
%e A363708 If a(7)=3: (1,2,1,3,2,3,3) would have the pair (3,3) enclosing 0 terms, yet 0 is never a term.
%e A363708 a(7)=4 without contradiction since 4 has not yet appeared in the sequence.
%e A363708 From _Kevin Ryde_, Jun 27 2023: (Start)
%e A363708 Backtracking can be illustrated at a(20) != 8. The following candidates are the actual a(1..19) followed by prospective 8 for a(20),
%e A363708     n  = ... 14 15 16 17 18 19 20
%e A363708   a(n) =  ... 2, 5, 4, 8, 7, 9, 8  <-- attempt a(20)=8
%e A363708 This is consistent if all of 2,5,4 pair with later terms so the 8's are pair number 14, gap a(14)=2.
%e A363708 But it turns out each possible value at a(21) makes such pair number 14 impossible, so no later terms can let this start work, and so must go back and change something.
%e A363708 (Logic could show in advance that 2,5 cannot both pair, but other impossible combinations might be more complex.)
%e A363708 (End)
%Y A363708 Cf. A363654, A026272, A363757.
%K A363708 nonn
%O A363708 1,2
%A A363708 _Neal Gersh Tolunsky_, Jun 16 2023
%E A363708 More terms from _Pontus von Brömssen_, Jun 29 2023