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

Author

Jan Koornstra, Mar 14 2020

Keywords

• nonn

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)

Examples

			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]
		

Crossrefs

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

Programs

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