A262278 - OEIS

%I #25 Dec 30 2020 12:23:27

%S 0,2,2,6,10,24,40,92,164,408,704,1674,3036,7002,12688,29040,53034,

%T 119502,219152,487924,900686,1984664,3683632,8039958,15012858,

%U 32477788,60988590,130889590,247193588,526601802,999873640,2115798292

%N Number of binary strings of length 2n that are squares, but are not expressible as the concatenation of two or more squares.

%C Here by a "square" we mean a string of the form xx, where x is any string, like the English word "hotshots".

%e For n = 4 the 10 strings are (0001)^2, (0010)^2, (0100)^2, (0110)^2, (0111)^2, and their complements.

%o (PARI)

%o MaxSquares(b,k)={if(b==0, k, my(r=-1); for(i=1, k, if(bitand(bitxor(b, b>>i), (1<<i)-1)==0, r=max(r, MaxSquares(b>>(2*i), k-i)))); if(r>=0,r+1,r))}

%o a(n)={my(s=0);for(i=0, 2^(n-1)-1, if(MaxSquares(bitor(i<<n,i), n)==1, s++));2*s} \\ _Andrew Howroyd_, Jun 18 2018

%o (Python)

%o from numba import njit

%o @njit() # comment out for n >= 32

%o def MS(b, k):

%o   if b == 0: return k

%o   r = -1

%o   for i in range(1, k+1):

%o     if ((b^(b>>i)) & ((1<<i)-1)) == 0:

%o       r = max(r, MS(b>>(2*i), k-i))

%o   return r+1 if r >= 0 else r

%o @njit() # comment out for n >= 32

%o def a(n):

%o   s = 0

%o   for i in range(int(2**(n-1))):

%o     s += MS((i<<n)|i, n)==1

%o   return 2*s

%o print([a(n) for n in range(18)]) # _Michael S. Branicky_, Dec 29 2020 after Andrew Hoyroyd

%Y Cf. A262068.

%K nonn,more

%O 0,2

%A _Jeffrey Shallit_, Sep 17 2015

%E Two more terms from _Jeffrey Shallit_, Dec 14 2015

%E a(12)-a(24) from _Andrew Howroyd_, Jun 18 2018

%E a(25)-a(31) from _Michael S. Branicky_, Dec 29 2020