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

Table of n, a(n) for n=1..40.

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 A091915 A123862

Adjacent sequences:  A323443 A323444 A323445 * A323447 A323448 A323449

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 May 28 18:24 EDT 2022. Contains 354122 sequences. (Running on oeis4.)