cp's OEIS Frontend

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

%I A333307 #27 May 03 2023 15:03:19
%S A333307 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,
%T A333307 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,
%U A333307 0,2,1,0,2,2,1,0,0,0,2,1,0,2
%N A333307 Lexicographically earliest sequence over {0,1,2} that has the shortest palindromic or square subsequence (see Comments for precise definition).
%C A333307 Formal definition, from _R. J. Mathar_, Nov 29 2020: (Start)
%C A333307 _Jan Koornstra_'s Python program does the following:
%C A333307 Consider the given terms a(1),...,a(n-1) and check for all three candidates c=a(n)=0,1,2 the following:
%C A333307 i) Derive the longest palindromic subsequence
%C A333307       a(i),a(i+1),...,a(n-1),c
%C A333307    by chopping initial terms of the sequence, that is,
%C A333307    take the smallest i such that c=a(i), a(n-1)=a(i+1), ...
%C A333307 ii) Derive the longest subsequence which is a square (word)
%C A333307       a(i),a(i+1),...,a(n-1),c
%C A333307    by chopping initial terms of the sequence, that is
%C A333307    take the smallest i such that [a(i),a(i+1),...] = [..., a(n-1),c]
%C A333307 The length of the longer of the two candidate subsequences "dominates" and is remembered for each c.
%C A333307 The c (out of the three candidates) where that dominating length is shortest becomes the actual a(n).
%C A333307 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)
%e A333307 a(5) = 1:
%e A333307   0 yields a palindromic subsequence of length 3: [0, 1, 0],
%e A333307   1 a square subsequence of length 2: [1, 1],
%e A333307   and 2 a square subsequence of length 6: [0, 1, 2, 0, 1, 2].
%e A333307 a(6) = 2:
%e A333307   0 yields a palindromic subsequence of length 4: [0, 1, 1, 0],
%e A333307   1 a palindromic subsequence of length 3: [1, 1, 1],
%e A333307   and 2 a palindromic subsequence of length 1: [2]
%o A333307 (Python)
%o A333307 def a333307(n):
%o A333307   seq = []
%o A333307   for k in range(n):
%o A333307     options = []
%o A333307     l = len(seq) + 1
%o A333307     for m in range(3): # base
%o A333307       palindrome, square = 0, 0
%o A333307       for i in range(l - 1): # palindrome
%o A333307         if seq[i::] + [m] == (seq[i::] + [m])[::-1]:
%o A333307           palindrome = l - i
%o A333307           break
%o A333307       for i in range(l // 2, -1, -1): # square
%o A333307         if seq[l - 2 * i: l - i] == seq[l - i:] + [m]:
%o A333307           square = 2 * i
%o A333307           break
%o A333307       options.append(max(palindrome, square))
%o A333307     seq.append(options.index(min(options)))
%o A333307   return seq
%o A333307 print(a333307(82))
%Y A333307 Cf. A007814, A100833, A006345, A157238, A283131, A007814, A333325.
%K A333307 nonn
%O A333307 0,3
%A A333307 _Jan Koornstra_, Mar 14 2020