login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A323446 Number of binary strings w of length n that cannot be written in the form xyz, with x,z both nonempty and xz a square. 1
2, 2, 4, 6, 8, 12, 16, 26, 36, 70, 104, 220, 372, 758, 1408, 2874, 5472, 11056, 21696, 43546, 86060, 172514, 343068, 686888, 1369484, 2740080, 5471464, 10945900, 21872228, 43749868, 87460604, 174931610, 349777232, 699576604, 1398973652, 2797992934, 5595603056, 11191292048, 22381785572, 44763754898 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,1
COMMENTS
A square is a nonempty block of the form XX.
LINKS
Michael S. Branicky, Python program
EXAMPLE
For n = 6 the 12 solutions are {000001, 000011, 000111, 001011, 001111, 011111} and their complements.
PROG
(Python) # see links for a faster, bit-based version
from itertools import product
def issquare(w):
if len(w) == 0 or len(w)%2 == 1: return False
return w[:len(w)//2] == w[len(w)//2:]
def c(b):
for leny in range(len(b)-2, 0, -2):
for offset in range(1, len(b)-leny):
if issquare(b[:offset] + b[offset+leny:]):
return False
return not issquare(b)
def a(n):
return 2*sum(1 for b in product("01", repeat=n-1) if c("1"+"".join(b)))
print([a(n) for n in range(1, 21)]) # Michael S. Branicky, Dec 07 2021
CROSSREFS
Sequence in context: A080054 A108494 A078578 * A018129 A361298 A091915
KEYWORD
nonn
AUTHOR
Jeffrey Shallit, Jan 15 2019
EXTENSIONS
a(21)-a(33) from Lars Blomberg, Jan 26 2019
a(32)-a(33) corrected and a(34)-a(40) from Michael S. Branicky, Dec 07 2021
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 20 09:35 EDT 2024. Contains 373515 sequences. (Running on oeis4.)