A377079 a(1)=1; thereafter a(n) is the smallest k for which the subsequence a(n-k..n-1) has a distinct ordinal transform from that of any other subsequence of the sequence thus far.

1, 1, 2, 2, 3, 4, 3, 4, 4, 4, 3, 4, 4, 5, 5, 5, 5, 4, 5, 6, 5, 5, 5, 6, 7, 5, 5, 6, 6, 7, 6, 6, 7, 6, 7, 5, 5, 6, 7, 6, 7, 8, 6, 6, 7, 7, 8, 9, 7, 6, 4, 5, 6, 5, 6, 7, 7, 7, 8, 6, 7, 7, 8, 9, 7, 8, 6, 7, 6, 7, 8, 9, 6, 7, 7, 6, 7, 8, 6, 6, 7, 8, 7, 8, 9, 10, 7

Offset

1,3

Comments

In other words, a(n) is the length of the shortest subsequence ending at a(n-1) which has a unique ordinal transform among all ordinal transforms of subsequences of the sequence thus far. Alternatively, this is (the length of the longest subsequence ending at a(n-1) whose ordinal transform has occurred before as that of another subsequence) plus 1.

Links

Neal Gersh Tolunsky, Table of n, a(n) for n = 1..10000

OEIS Wiki, Ordinal Transform.

Neal Gersh Tolunsky, Ordinal Transform of 500000 terms

Example

a(8)=4 because the length-4 subsequence a(4..7) = 2,3,4,3 has the shortest unique ordinal transform (1,1,1,2), which does not occur elsewhere as the ordinal transform of any other subsequence in the sequence thus far. No shorter subsequence ending in a(7) with a unique ordinal transform exists in the sequence thus far. For example, a(8) cannot be 3 because the length-3 subsequence a(5..7) = 3,4,3 has the same ordinal transform (1,1,2) as that of the subsequence a(2..4) = 1,2,2.

Prog

(Python)
from itertools import count, islice
def ot(t): # after ORDINAL at https://oeis.org/wiki/Ordinal_transform
    c={}; return tuple(c.setdefault(x, c.pop(x, 0)+1) for x in t)
def agen(): # generator of terms
    a, R, maxL = [1], set(), 0  # maxL = max length of ot's stored
    for n in count(1):
        yield a[-1]
        for k in range(1, n+1):
            if k > maxL:  # must increase length of ot's stored
                maxL += 1
                R.update(ot(a[i:i+maxL]) for i in range(n-maxL))
            if ot(a[-k:]) not in R:
                break
        an = k
        R.update(ot(a[-i:]) for i in range(1, maxL+1))
        a.append(an)
print(list(islice(agen(), 90))) # Michael S. Branicky, Oct 15 2024

Crossrefs

Cf. A376937, A375207.

Sequence in context: A056796 A061295 A081742 * A127432 A199408 A285325

Adjacent sequences: A377076 A377077 A377078 * A377080 A377081 A377082

Keyword

nonn

Author

Neal Gersh Tolunsky, Oct 15 2024

Status

approved