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

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

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 rhyme scheme among all rhyme schemes of subsequences of the sequence thus far. Alternatively, this is (the length of the longest subsequence ending at a(n-1) whose rhyme scheme has occurred before as that of another subsequence) plus 1.

The rhyme scheme of a subsequence is found by assigning 1 to the first unique value, 2 to the second unique value, 3 to the third, and so on.

Links

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

Neal Gersh Tolunsky, Ordinal Transform of 500000 terms

Example

a(6)=4 because the length-4 subsequence a(2..5) = 1,2,2,3 has the shortest unique rhyme scheme (1,2,2,3 or A,B,B,C,) which does not occur elsewhere as the rhyme scheme of any other subsequence in the sequence thus far. No shorter subsequence ending in a(5) with a unique rhyme scheme exists in the sequence thus far. For example, a(6) cannot be 3 because the length-3 subsequence a(3..5) = 2,2,3 has the same rhyme scheme (1,1,2 or A,A,B) as that of the subsequence a(1..3) = 1,1,2.

Prog

(Python)
from itertools import count, islice
def rs(t): # rhyme scheme of t
    s, k, m  = [], 1, dict()
    for e in t:
        if e not in m: m[e] = k; k += 1
        s.append(m[e])
    return tuple(s)
def agen(): # generator of terms
    a, R, maxL = [1], set(), 0  # maxL = max length of rhyme schemes stored
    for n in count(1):
        yield a[-1]
        for k in range(1, n+1):
            if k > maxL:  # must increase length of rhyme schemes stored
                maxL += 1
                R.update(rs(a[i:i+maxL]) for i in range(n-maxL))
            if rs(a[-k:]) not in R:
                break
        an = k
        R.update(rs(a[-i:]) for i in range(1, maxL+1))
        a.append(an)
print(list(islice(agen(), 90))) # Michael S. Branicky, Oct 13 2024

Crossrefs

Cf. A377079, A375207, A120698 (rhyme schemes), A000110.

Sequence in context: A374993 A374995 A350238 * A374994 A374992 A352746

Adjacent sequences: A376934 A376935 A376936 * A376938 A376939 A376940

Keyword

nonn

Author

Neal Gersh Tolunsky, Oct 11 2024

Status

approved