cp's OEIS Frontend

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.

%I A376937 #29 Nov 02 2024 00:06:27
%S A376937 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,
%T A376937 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,
%U A376937 6,5,5,5,5,6,6,5,6,7,8,6,6,7,8,5,6,7,8,9,9
%N 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.
%C A376937 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.
%C A376937 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.
%H A376937 Neal Gersh Tolunsky, <a href="/A376937/b376937.txt">Table of n, a(n) for n = 1..10000</a>
%H A376937 Neal Gersh Tolunsky, <a href="/A376937/a376937_1.png">Ordinal Transform of 500000 terms</a>
%e A376937 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.
%o A376937 (Python)
%o A376937 from itertools import count, islice
%o A376937 def rs(t): # rhyme scheme of t
%o A376937     s, k, m  = [], 1, dict()
%o A376937     for e in t:
%o A376937         if e not in m: m[e] = k; k += 1
%o A376937         s.append(m[e])
%o A376937     return tuple(s)
%o A376937 def agen(): # generator of terms
%o A376937     a, R, maxL = [1], set(), 0  # maxL = max length of rhyme schemes stored
%o A376937     for n in count(1):
%o A376937         yield a[-1]
%o A376937         for k in range(1, n+1):
%o A376937             if k > maxL:  # must increase length of rhyme schemes stored
%o A376937                 maxL += 1
%o A376937                 R.update(rs(a[i:i+maxL]) for i in range(n-maxL))
%o A376937             if rs(a[-k:]) not in R:
%o A376937                 break
%o A376937         an = k
%o A376937         R.update(rs(a[-i:]) for i in range(1, maxL+1))
%o A376937         a.append(an)
%o A376937 print(list(islice(agen(), 90))) # _Michael S. Branicky_, Oct 13 2024
%Y A376937 Cf. A377079, A375207, A120698 (rhyme schemes), A000110.
%K A376937 nonn
%O A376937 1,3
%A A376937 _Neal Gersh Tolunsky_, Oct 11 2024