A333307 Lexicographically earliest sequence over {0,1,2} that has the shortest palindromic or square subsequence (see Comments for precise definition).

0, 1, 2, 0, 1, 1, 2, 0, 0, 1, 2, 0, 1, 1, 2, 2, 0, 1, 2, 0, 0, 1, 2, 2, 0, 1, 2, 0, 2, 2, 1, 0, 2, 1, 1, 0, 2, 2, 1, 0, 2, 1, 2, 2, 0, 1, 2, 0, 0, 1, 2, 2, 0, 1, 2, 0, 2, 2, 1, 0, 2, 1, 1, 0, 2, 2, 1, 0, 0, 2, 1, 0, 2, 2, 1, 0, 0, 0, 2, 1, 0, 2

Offset

0,3

Comments

Formal definition, from R. J. Mathar, Nov 29 2020: (Start)

Jan Koornstra's Python program does the following:

Consider the given terms a(1),...,a(n-1) and check for all three candidates c=a(n)=0,1,2 the following:

i) Derive the longest palindromic subsequence

a(i),a(i+1),...,a(n-1),c

by chopping initial terms of the sequence, that is,

take the smallest i such that c=a(i), a(n-1)=a(i+1), ...

ii) Derive the longest subsequence which is a square (word)

a(i),a(i+1),...,a(n-1),c

by chopping initial terms of the sequence, that is

take the smallest i such that [a(i),a(i+1),...] = [..., a(n-1),c]

The length of the longer of the two candidate subsequences "dominates" and is remembered for each c.

The c (out of the three candidates) where that dominating length is shortest becomes the actual a(n).

So the principle is like selecting 0, 1, or 2 by trying to keep the end of the current sequence as much as possible out of tune with being square or palindromic. (End)

Links

Table of n, a(n) for n=0..81.

Example

a(5) = 1:
  0 yields a palindromic subsequence of length 3: [0, 1, 0],
  1 a square subsequence of length 2: [1, 1],
  and 2 a square subsequence of length 6: [0, 1, 2, 0, 1, 2].
a(6) = 2:
  0 yields a palindromic subsequence of length 4: [0, 1, 1, 0],
  1 a palindromic subsequence of length 3: [1, 1, 1],
  and 2 a palindromic subsequence of length 1: [2]

Prog

(Python)
def a333307(n):
  seq = []
  for k in range(n):
    options = []
    l = len(seq) + 1
    for m in range(3): # base
      palindrome, square = 0, 0
      for i in range(l - 1): # palindrome
        if seq[i::] + [m] == (seq[i::] + [m])[::-1]:
          palindrome = l - i
          break
      for i in range(l // 2, -1, -1): # square
        if seq[l - 2 * i: l - i] == seq[l - i:] + [m]:
          square = 2 * i
          break
      options.append(max(palindrome, square))
    seq.append(options.index(min(options)))
  return seq
print(a333307(82))

Crossrefs

Cf. A007814, A100833, A006345, A157238, A283131, A007814, A333325.

Sequence in context: A077614 A336396 A280379 * A180793 A352523 A116948

Adjacent sequences: A333304 A333305 A333306 * A333308 A333309 A333310

Keyword

nonn

Author

Jan Koornstra, Mar 14 2020

Status

approved