A seq with a strange behavior (or not)?

A 3 from a tree

Hello Math-Fun,

NAME

Lexicographically earliest sequence of positive integers such that the nth pair of identical terms encloses exactly a(n) terms.

DATA

S = 1, 2, 1, 3, 2, 3, 1, 2, 4, 3, 4, 5, 3, 6, 7, 4, 3, 8, 6, 9, 7, 8, 4, 10, 3, 7, 4, 6, 8, 9, …

COMMENTS

To extend S we try first to find the smallest existing term that doesn’t lead to a contradiction. If all existing terms lead to a contradiction, we try the smallest term not present in S that doesn’t lead to a contradiction.

EXAMPLE

For n = 1, we have a(1) = 1 and the 1st constructed pair encloses 1 term: [1, 2, 1]

For n = 2, we have a(2) = 2 and the 2nd constructed pair encloses 2 terms: [2, 1, 3, 2]

For n = 3, we have a(3) = 1 and the 3rd constructed pair encloses 1 term: [3, 2, 3]

For n = 4, we have a(4) = 3 and the 4th constructed pair encloses 3 terms: [1, 3, 2, 3, 1]

For n = 5, we have a(5) = 2 and the 5th constructed pair encloses 2 terms: [2, 3, 1, 2]

For n = 6, we have a(6) = 3 and the 6th constructed pair encloses 3 terms: [3, 1, 2, 4, 3]

For n = 7, we have a(7) = 1 and the 7th constructed pair encloses 1 term: [4, 3, 4]

etc.

Why is the word *constructed* present in the above Example section?

Imagine a person A checking if S works as intended.

A will read S term by term and ask itself at every stage: to what *enclosing pair* does this a(n) belong?

Well, a(1) = 1 will be interpreted as the *opening bracket* of the first pair [1,1]; A will then check how many integers are enclosed by [1, 1] (answer: one integer, which is correct, the integer 2).

A would then read (from left to right) a(2) = 2 as the *opening bracket* of the second pair [2,2], then check how many integers are enclosed by [2, 2] (answer: two integers, which is correct, the integers 1 and 3).

Now comes a(3) = 1, which A might (incorrectly) see as the *opening bracket* of the third pair [1,1] — instead of the *closing bracket* of the first pair! If A, looking to the right, checks how many integers are enclosed by the next [1, 1], A will think that something is wrong: _three_ integers are enclosed there (the integers 3, 2, 3), which doesn’t match the value _1_ of a(3).

The word *constructed* is intended to avoid the above misinterpretation.

Indeed, when building the start of S, the third pair to appear was [3, 3], correctly enclosing _one_ single integer, which is a(5) = 2.

_Then_ was built the fourth pair [1, 1], correctly enclosing the _three_ integers 3, 2 and 3… See the hereunder way of building S.

__________________________________

Successive enclosing pairs (in yellow) and enclosed terms (in blue + underlined); the successive sizes of the blue underlined chunks reproduce the sequence S itself:

[Chunk size]

S = 1, 2, 1, 3, 2, 3, 1, 2, 4, 3, 4, 5, 3, 6, 7, 4, 3, 8, 6, 9, 7, 8, 4, 10, 3, 7, 4, 6, 8, 9, … [1]

S = 1, 2, 1, 3, 2, 3, 1, 2, 4, 3, 4, 5, 3, 6, 7, 4, 3, 8, 6, 9, 7, 8, 4, 10, 3, 7, 4, 6, 8, 9, … [2]

S = 1, 2, 1, 3, 2, 3, 1, 2, 4, 3, 4, 5, 3, 6, 7, 4, 3, 8, 6, 9, 7, 8, 4, 10, 3, 7, 4, 6, 8, 9, … [1]