|
%I #23 Mar 30 2022 06:36:17
%S 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,
%T 12,8,12,6,10,4,6,2,4,2,4
%N The number of strong binary words of length n.
%C 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].
%C 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.
%C Terms are even since if w is a strong binary word, then so is its binary complement. - _Michael S. Branicky_, Mar 29 2022
%H Tero Harju, Tomi Kärki and Dirk Nowotka, <a href="https://doi.org/10.37236/493">The Number of Positions Starting a Square in Binary Words</a>, The Electronic Journal of Combinatorics, 18 (2011), #P6.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/SquarefreeWord.html">Squarefree Word</a>
%e 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.
%o (Python)
%o def s(u, w): # sigma_w(u) in Harju et al., p. 2
%o 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)))
%o def is_strong(w):
%o return all(2*s(u, w)>=len(u) for u in (w[:i+1] for i in range(len(w))))
%o def aupton(terms):
%o alst, strong = [2], ["0"]
%o for n in range(terms):
%o strong = [w+b for w in strong for b in "01" if is_strong(w+b)]
%o alst.append(2*len(strong))
%o return alst
%o print(aupton(80)) # _Michael S. Branicky_, Mar 29 2022
%K nonn,fini,full
%O 1,1
%A _John W. Layman_, May 27 2011
|
