A262068 Number of binary strings of length 2n that can be written as the concatenation of one or more squares.

1, 2, 6, 22, 76, 268, 926, 3250, 11328, 39658, 138534, 484364, 1693078, 5918780, 20690230, 72328158, 252841374, 883869956, 3089791576, 10801141656

Offset

0,2

Comments

By a "square" we mean a word of the form xx, where x is a string, like the English word "murmur".

a(0)=1 is by convention. - N. J. A. Sloane, Sep 17 2015

Links

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

Example

For n = 2 the six words are 0000, 0011, 0101, and their complements.

Maple

for n from 1 to 13 do
B[n]:= convert(map(t-> t||t, StringTools:-Generate(n, "01")), set);
od:
C[0]:= {""}:
for n from 1 to 13 do
  C[n]:= {seq(seq(seq(cat(s, t), s=B[i]), t = C[n-i]), i=1..n)};
od:
seq(nops(C[n]), n=0..13); # Robert Israel, Sep 17 2015

Prog

(Python) # MS() in A262278
from numba import njit
@njit()  # comment out for n >= 32
def a(n):
  if n == 0: return 1  # by convention
  s = 0
  for b in range(int(2**(2*n-1))):
    s += MS(b, n) >= 1
  return 2*s
print([a(n) for n in range(10)]) # Michael S. Branicky, Dec 29 2020

Crossrefs

Cf. A262278.

Sequence in context: A109194 A014334 A107239 * A148496 A217528 A181367

Adjacent sequences: A262065 A262066 A262067 * A262069 A262070 A262071

Keyword

nonn,more

Author

Jeffrey Shallit, Sep 17 2015

Extensions

a(14)-a(19) from Lars Blomberg, Feb 03 2019

Status

approved