A191234 The number of strong binary words of length n.

2, 2, 4, 4, 8, 6, 12, 8, 12, 10, 16, 8, 12, 10, 16, 14, 20, 12, 18, 12, 20, 18, 26, 14, 20, 8, 12, 8, 12, 6, 10, 4, 6, 2, 4, 2, 4

Offset

1,1

Comments

Let s(w) denote the number of positions in a word that do not start a square. Then a word is said to be strong if for all nonempty prefixes u of w we have s_w(u) >= |u|/2 [see Harju et al., p. 2].

The authors of the linked paper show that a(n) = 0 for n > 37, and thus all terms are known. For this reason the sequence is assigned the keyword "full" although it is actually not a finite sequence.

Terms are even since if w is a strong binary word, then so is its binary complement. - Michael S. Branicky, Mar 29 2022

Links

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

Tero Harju, Tomi Kärki and Dirk Nowotka, The Number of Positions Starting a Square in Binary Words, The Electronic Journal of Combinatorics, 18 (2011), #P6.

Eric Weisstein's World of Mathematics, Squarefree Word

Example

Consider the binary word 0110 of length 4. The prefixes 0, 01, 011, and 0110 have 1, 2, 2, and 2 squarefree positions with ratios to length of 1, 1, 2/3, and 1/2, respectively. Since each ratio is greater than or equal to 1/2, 0110 is strong.

Prog

(Python)
def s(u, w): # sigma_w(u) in Harju et al., p. 2
    return sum(1 for i in range(len(u)) if not any(w[i:i+j] == w[i+j:i+2*j] for j in range(1, (len(w)-i)//2+1)))
def is_strong(w):
    return all(2*s(u, w)>=len(u) for u in (w[:i+1] for i in range(len(w))))
def aupton(terms):
    alst, strong = [2], ["0"]
    for n in range(terms):
        strong = [w+b for w in strong for b in "01" if is_strong(w+b)]
        alst.append(2*len(strong))
    return alst
print(aupton(80)) # Michael S. Branicky, Mar 29 2022

Crossrefs

Sequence in context: A353125 A330807 A008330 * A225373 A138219 A279405

Adjacent sequences: A191231 A191232 A191233 * A191235 A191236 A191237

Keyword

nonn,fini,full

Author

John W. Layman, May 27 2011

Status

approved