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.

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, 15, 13, 11, 12, 14, 16, 2, 17, 10, 2, 18, 15, 12, 13, 19, 20, 21, 14, 17, 22, 23, 17, 10, 24, 2, 13, 12, 15, 20, 12, 25, 21, 17, 26, 14, 27, 28, 22, 29, 30, 31, 32

Offset: 1

Author

Neal Gersh Tolunsky, Jun 16 2023

Keywords

• nonn

Comments

Calculating terms may require backtracking, since pair numbers are not fixed until enough later terms either do or don't pair with earlier terms.

Examples

			The first pair (1,2,1) encloses 1 term because a(1)=1.
The second pair (2,1,3,2) encloses 2 terms because a(2)=2.
The third pair (3,2,3) encloses 1 term because a(3)=1.
The fourth pair (2,3,4,5,2) encloses 3 terms because a(4)=3.
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.
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).
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.
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.
a(7)=4 without contradiction since 4 has not yet appeared in the sequence.
From _Kevin Ryde_, Jun 27 2023: (Start)
Backtracking can be illustrated at a(20) != 8. The following candidates are the actual a(1..19) followed by prospective 8 for a(20),
    n  = ... 14 15 16 17 18 19 20
  a(n) =  ... 2, 5, 4, 8, 7, 9, 8  <-- attempt a(20)=8
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.
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.
(Logic could show in advance that 2,5 cannot both pair, but other impossible combinations might be more complex.)
(End)
		

Links

• Pontus von Brömssen, Table of n, a(n) for n = 1..200

Crossrefs

Cf. A363654, A026272, A363757.

Extensions

More terms from Pontus von Brömssen, Jun 29 2023