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
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
KEYWORD
nonn,fini,full
AUTHOR
John W. Layman, May 27 2011
STATUS
approved