login
A333307
Lexicographically earliest sequence over {0,1,2} that has the shortest palindromic or square subsequence (see Comments for precise definition).
2
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)
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))
KEYWORD
nonn
AUTHOR
Jan Koornstra, Mar 14 2020
STATUS
approved