A375207 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.

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, 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, 5, 5, 5, 5, 5, 6, 6, 7, 8, 9, 10, 10, 6, 2, 3, 3, 4, 5, 6, 7

Offset

1,3

Comments

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.

Links

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

Neal Gersh Tolunsky, Ordinal Transform of 500000 terms

Example

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.
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).

Prog

(Python)
from itertools import count, islice
def fd(t): return tuple(t[i]-t[i-1] for i in range(1, len(t)))
def agen(): # generator of terms
    a, R, maxL = [1], set(), 0  # maxL = max length of first diff.'s stored
    for n in count(1):
        yield a[-1]
        for k in range(1, n+1):
            if k > maxL:  # must increase length of first diff.'s stored
                maxL += 1
                R.update(fd(a[i:i+maxL]) for i in range(n-maxL))
            if fd(a[-k:]) not in R:
                break
        an = k
        R.update(fd(a[-i:]) for i in range(1, maxL+1))
        a.append(an)
print(list(islice(agen(), 90))) # Michael S. Branicky, Oct 16 2024

Crossrefs

Cf. A377079, A376937.

Sequence in context: A333389 A352286 A352259 * A245909 A077769 A286543

Adjacent sequences: A375203 A375204 A375206 * A375209 A375212 A375213

Keyword

nonn

Author

Neal Gersh Tolunsky, Oct 16 2024

Status

approved