A333307 - OEIS

%I #27 May 03 2023 15:03:19

%S 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 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 0,2,1,0,2,2,1,0,0,0,2,1,0,2

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

%C Formal definition, from _R. J. Mathar_, Nov 29 2020: (Start)

%C _Jan Koornstra_'s Python program does the following:

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

%C i) Derive the longest palindromic subsequence

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

%C    by chopping initial terms of the sequence, that is,

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

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

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

%C    by chopping initial terms of the sequence, that is

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

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

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

%C 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 a(5) = 1:

%e   0 yields a palindromic subsequence of length 3: [0, 1, 0],

%e   1 a square subsequence of length 2: [1, 1],

%e   and 2 a square subsequence of length 6: [0, 1, 2, 0, 1, 2].

%e a(6) = 2:

%e   0 yields a palindromic subsequence of length 4: [0, 1, 1, 0],

%e   1 a palindromic subsequence of length 3: [1, 1, 1],

%e   and 2 a palindromic subsequence of length 1: [2]

%o (Python)

%o def a333307(n):

%o   seq = []

%o   for k in range(n):

%o     options = []

%o     l = len(seq) + 1

%o     for m in range(3): # base

%o       palindrome, square = 0, 0

%o       for i in range(l - 1): # palindrome

%o         if seq[i::] + [m] == (seq[i::] + [m])[::-1]:

%o           palindrome = l - i

%o           break

%o       for i in range(l // 2, -1, -1): # square

%o         if seq[l - 2 * i: l - i] == seq[l - i:] + [m]:

%o           square = 2 * i

%o           break

%o       options.append(max(palindrome, square))

%o     seq.append(options.index(min(options)))

%o   return seq

%o print(a333307(82))

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

%K nonn

%O 0,3

%A _Jan Koornstra_, Mar 14 2020