cp's OEIS Frontend

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.

%I A377079 #14 Nov 01 2024 18:31:37
%S A377079 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,
%T A377079 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,
%U A377079 6,7,8,9,6,7,7,6,7,8,6,6,7,8,7,8,9,10,7
%N 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.
%C A377079 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.
%H A377079 Neal Gersh Tolunsky, <a href="/A377079/b377079.txt">Table of n, a(n) for n = 1..10000</a>
%H A377079 OEIS Wiki, <a href="https://oeis.org/wiki/Ordinal_transform">Ordinal Transform</a>.
%H A377079 Neal Gersh Tolunsky, <a href="/A377079/a377079.png">Ordinal Transform of 500000 terms</a>
%e A377079 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.
%o A377079 (Python)
%o A377079 from itertools import count, islice
%o A377079 def ot(t): # after ORDINAL at https://oeis.org/wiki/Ordinal_transform
%o A377079     c={}; return tuple(c.setdefault(x, c.pop(x, 0)+1) for x in t)
%o A377079 def agen(): # generator of terms
%o A377079     a, R, maxL = [1], set(), 0  # maxL = max length of ot's stored
%o A377079     for n in count(1):
%o A377079         yield a[-1]
%o A377079         for k in range(1, n+1):
%o A377079             if k > maxL:  # must increase length of ot's stored
%o A377079                 maxL += 1
%o A377079                 R.update(ot(a[i:i+maxL]) for i in range(n-maxL))
%o A377079             if ot(a[-k:]) not in R:
%o A377079                 break
%o A377079         an = k
%o A377079         R.update(ot(a[-i:]) for i in range(1, maxL+1))
%o A377079         a.append(an)
%o A377079 print(list(islice(agen(), 90))) # _Michael S. Branicky_, Oct 15 2024
%Y A377079 Cf. A376937, A375207.
%K A377079 nonn
%O A377079 1,3
%A A377079 _Neal Gersh Tolunsky_, Oct 15 2024