|
%I #70 Dec 30 2020 02:59:21
%S 1,2,6,22,76,268,926,3250,11328,39658,138534,484364,1693078,5918780,
%T 20690230,72328158,252841374,883869956,3089791576,10801141656
%N Number of binary strings of length 2n that can be written as the concatenation of one or more squares.
%C By a "square" we mean a word of the form xx, where x is a string, like the English word "murmur".
%C a(0)=1 is by convention. - _N. J. A. Sloane_, Sep 17 2015
%e For n = 2 the six words are 0000, 0011, 0101, and their complements.
%p for n from 1 to 13 do
%p B[n]:= convert(map(t-> t||t, StringTools:-Generate(n,"01")), set);
%p od:
%p C[0]:= {""}:
%p for n from 1 to 13 do
%p C[n]:= {seq(seq(seq(cat(s,t), s=B[i]), t = C[n-i]), i=1..n)};
%p od:
%p seq(nops(C[n]), n=0..13); # _Robert Israel_, Sep 17 2015
%o (Python) # MS() in A262278
%o from numba import njit
%o @njit() # comment out for n >= 32
%o def a(n):
%o if n == 0: return 1 # by convention
%o s = 0
%o for b in range(int(2**(2*n-1))):
%o s += MS(b, n) >= 1
%o return 2*s
%o print([a(n) for n in range(10)]) # _Michael S. Branicky_, Dec 29 2020
%Y Cf. A262278.
%K nonn,more
%O 0,2
%A _Jeffrey Shallit_, Sep 17 2015
%E a(14)-a(19) from _Lars Blomberg_, Feb 03 2019
|
