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

0, 2, 2, 6, 10, 24, 40, 92, 164, 408, 704, 1674, 3036, 7002, 12688, 29040, 53034, 119502, 219152, 487924, 900686, 1984664, 3683632, 8039958, 15012858, 32477788, 60988590, 130889590, 247193588, 526601802, 999873640, 2115798292

Offset

0,2

Comments

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

Links

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

Example

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

Prog

(PARI)
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))}
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
(Python)
from numba import njit
@njit() # comment out for n >= 32
def MS(b, k):
  if b == 0: return k
  r = -1
  for i in range(1, k+1):
    if ((b^(b>>i)) & ((1<<i)-1)) == 0:
      r = max(r, MS(b>>(2*i), k-i))
  return r+1 if r >= 0 else r
@njit() # comment out for n >= 32
def a(n):
  s = 0
  for i in range(int(2**(n-1))):
    s += MS((i<<n)|i, n)==1
  return 2*s
print([a(n) for n in range(18)]) # Michael S. Branicky, Dec 29 2020 after Andrew Hoyroyd

Crossrefs

Cf. A262068.

Sequence in context: A151575 A014113 A284462 * A265639 A208900 A229733

Adjacent sequences: A262275 A262276 A262277 * A262279 A262280 A262281

Keyword

nonn,more

Author

Jeffrey Shallit, Sep 17 2015

Extensions

Two more terms from Jeffrey Shallit, Dec 14 2015

a(12)-a(24) from Andrew Howroyd, Jun 18 2018

a(25)-a(31) from Michael S. Branicky, Dec 29 2020

Status

approved