|
|
A262278
|
|
Number of binary strings of length 2n that are squares, but are not expressible as the concatenation of two or more squares.
|
|
1
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|