# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/

Search: id:a229614
Showing 1-1 of 1

%I A229614 #42 Nov 14 2021 03:30:03
%S A229614 1,2,4,8,16,32,56,104,178,314,536,930,1558,2666,4482,7574,12686,21360,
%T A229614 35812,60152,100812,169122,283498,475356,796292,1334558,2235888,
%U A229614 3746534,6276048,10515080,17614726,29510362,49434792,82815016,138729368,232399846,389306052
%N A229614 Number of binary strings of length n avoiding "squares" (that is, repeated blocks of the form xx) with |x| > 2.
%C A229614 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
%C A229614 For n >= 1, terms are even by symmetry. - _Michael S. Branicky_, Nov 11 2021
%H A229614 Michael S. Branicky, <a href="/A229614/b229614.txt">Table of n, a(n) for n = 0..42</a>
%H A229614 Michael S. Branicky, <a href="/A229614/a229614.py.txt">Python program</a>
%H A229614 R. C. Entringer, D. E. Jackson and J. A. Schatz, <a href="http://dx.doi.org/10.1016/0097-3165(74)90041-7">On nonrepetitive sequences</a>, J. Combin. Theory Ser. A. 16 (1974), 159-164.
%e A229614 For n = 6 there are 8 strings omitted, namely 000000, 001001, ..., 111111, so a(6) = 64 - 8 = 56.
%t A229614 a[n_] := a[n] = Select[PadLeft[#, n]& /@ IntegerDigits[Range[0, 2^n-1], 2], {} == SequencePosition[#, {b__, b__} /; Length[{b}] >= 3, 1]&] // Length;
%t A229614 Table[Print[n, " ", a[n]]; a[n], {n, 0, 22}] (* _Jean-François Alcover_, Nov 11 2021 *)
%o A229614 (Python) # see link for a faster program based on binary operations
%o A229614 def isf(s): # incrementally squarefree (check factors ending in last letter)
%o A229614     for l in range(3, len(s)//2 + 1):
%o A229614         if s[-2*l:-l] == s[-l:]: return False
%o A229614     return True
%o A229614 def aupton(nn, verbose=False):
%o A229614     alst, sfs = [1], set("0")
%o A229614     for n in range(1, nn+1):
%o A229614         an = 2*len(sfs) # by symmetry
%o A229614         sfsnew = set(s+i for s in sfs for i in "01" if isf(s+i))
%o A229614         alst, sfs = alst+[an], sfsnew
%o A229614         if verbose: print(n, an)
%o A229614     return alst
%o A229614 print(aupton(24)) # _Michael S. Branicky_, Nov 11 2021
%Y A229614 Cf. A230127, A230177, A230216.
%K A229614 nonn
%O A229614 0,2
%A A229614 _Jeffrey Shallit_, Sep 26 2013
%E A229614 a(23)-a(36) from _Nathaniel Johnston_, Oct 10 2013

# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE