VOOZH about

URL: https://oeis.org/A229614

⇱ A229614 - OEIS

login
A229614
Number of binary strings of length n avoiding "squares" (that is, repeated blocks of the form xx) with |x| > 2.
4
1, 2, 4, 8, 16, 32, 56, 104, 178, 314, 536, 930, 1558, 2666, 4482, 7574, 12686, 21360, 35812, 60152, 100812, 169122, 283498, 475356, 796292, 1334558, 2235888, 3746534, 6276048, 10515080, 17614726, 29510362, 49434792, 82815016, 138729368, 232399846, 389306052
OFFSET
0,2
COMMENTS
Entringer et al. showed that this sequence is always nonzero (in contrast with A230127, which is zero for all n >= 19). - Nathaniel Johnston, Oct 10 2013
For n >= 1, terms are even by symmetry. - Michael S. Branicky, Nov 11 2021
LINKS
Michael S. Branicky, Table of n, a(n) for n = 0..42
Michael S. Branicky, Python program
R. C. Entringer, D. E. Jackson and J. A. Schatz, On nonrepetitive sequences, J. Combin. Theory Ser. A. 16 (1974), 159-164.
EXAMPLE
For n = 6 there are 8 strings omitted, namely 000000, 001001, ..., 111111, so a(6) = 64 - 8 = 56.
MATHEMATICA
a[n_] := a[n] = Select[PadLeft[#, n]& /@ IntegerDigits[Range[0, 2^n-1], 2], {} == SequencePosition[#, {b__, b__} /; Length[{b}] >= 3, 1]&] // Length;
Table[Print[n, " ", a[n]]; a[n], {n, 0, 22}] (* Jean-François Alcover, Nov 11 2021 *)
PROG
(Python) # see link for a faster program based on binary operations
def isf(s): # incrementally squarefree (check factors ending in last letter)
for l in range(3, len(s)//2 + 1):
if s[-2*l:-l] == s[-l:]: return False
return True
def aupton(nn, verbose=False):
alst, sfs = [1], set("0")
for n in range(1, nn+1):
an = 2*len(sfs) # by symmetry
sfsnew = set(s+i for s in sfs for i in "01" if isf(s+i))
alst, sfs = alst+[an], sfsnew
if verbose: print(n, an)
return alst
print(aupton(24)) # Michael S. Branicky, Nov 11 2021
CROSSREFS
KEYWORD
nonn
AUTHOR
Jeffrey Shallit, Sep 26 2013
EXTENSIONS
a(23)-a(36) from Nathaniel Johnston, Oct 10 2013
STATUS
approved