A375207 - OEIS

%I #11 Nov 02 2024 00:05:33

%S 1,1,2,2,3,4,3,2,3,3,4,5,6,4,2,3,3,4,5,6,7,5,6,4,4,3,3,3,3,4,4,5,6,7,

%T 7,4,2,3,4,4,5,5,5,4,4,5,4,4,4,5,5,6,7,8,9,8,5,3,4,5,6,5,6,4,4,5,4,5,

%U 5,5,5,5,5,6,6,7,8,9,10,10,6,2,3,3,4,5,6,7

%N a(1)=1; thereafter a(n) is the smallest k for which the subsequence a(n-k..n-1) has a distinct sequence of first differences from that of any other subsequence of the sequence thus far.

%C In other words, a(n) is the length of the shortest subsequence ending at a(n-1) which has unique first differences among all first differences of subsequences of the sequence thus far.

%H Neal Gersh Tolunsky, <a href="/A375207/b375207.txt">Table of n, a(n) for n = 1..10000</a>

%H Neal Gersh Tolunsky, <a href="/A375207/a375207.png">Ordinal Transform of 500000 terms</a>

%e a(8)=2 because the length-2 subsequence a(6..7) = 4,3 has the shortest unique first differences (-1) of any other subsequence in the sequence thus far.

%e a(9)=3 because the length-3 subsequence a(6..8) = 4,3,2 likewise has the shortest unique first differences (-1,-1). No shorter subsequence ending in a(8) with unique first differences exists in the sequence thus far. We cannot have, for example, a(7..8) = 3,2 since we saw a subsequence with the same first differences in the previous example, where a(6..7) = 4,3 has first difference (-1).

%o (Python)

%o from itertools import count, islice

%o def fd(t): return tuple(t[i]-t[i-1] for i in range(1, len(t)))

%o def agen(): # generator of terms

%o     a, R, maxL = [1], set(), 0  # maxL = max length of first diff.'s stored

%o     for n in count(1):

%o         yield a[-1]

%o         for k in range(1, n+1):

%o             if k > maxL:  # must increase length of first diff.'s stored

%o                 maxL += 1

%o                 R.update(fd(a[i:i+maxL]) for i in range(n-maxL))

%o             if fd(a[-k:]) not in R:

%o                 break

%o         an = k

%o         R.update(fd(a[-i:]) for i in range(1, maxL+1))

%o         a.append(an)

%o print(list(islice(agen(), 90))) # _Michael S. Branicky_, Oct 16 2024

%Y Cf. A377079, A376937.

%K nonn

%O 1,3

%A _Neal Gersh Tolunsky_, Oct 16 2024