A297702 Number of length-n binary strings where every prefix is either a palindrome, or the concatenation of two palindromes.

1, 2, 4, 8, 16, 32, 52, 88, 134, 184, 254, 342, 422, 530, 658, 770, 922, 1090, 1248, 1438, 1640, 1834, 2090, 2334, 2570, 2842, 3158, 3432, 3762, 4104, 4438, 4810, 5210, 5568, 6022, 6420, 6858, 7344, 7852, 8292, 8816, 9352, 9894, 10448, 11056, 11584, 12274, 12880, 13498, 14168, 14886, 15530, 16298, 17002, 17754

Offset

0,2

Links

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

Example

For n = 6 the 12 missing strings are 001011,001101,010011,010110,011001,011010 and their bitwise complements.

Maple

g:= proc(L) local k;
  if L = ListTools:-Reverse(L) then return true fi;
  for k from 1 to nops(L)-1 do
    if L[1..k]=ListTools:-Reverse(L[1..k]) and L[k+1..-1] = ListTools:-Reverse(L[k+1..-1]) then return true fi;
  od:
  false
end proc:
A[0]:= 1: S:= [[]]:
for n from 1 to 55 do
  S:= select(g, map(t -> ([op(t), 0], [op(t), 1]), S));
  A[n]:= nops(S);
od:
seq(A[i], i=0..55); # Robert Israel, Jan 03 2018

Crossrefs

Sequence in context: A217833 A226930 A326751 * A306314 A007055 A175951

Adjacent sequences: A297699 A297700 A297701 * A297703 A297704 A297705

Keyword

nonn

Author

Jeffrey Shallit, Jan 03 2018

Status

approved