A230127 -id:A230127 - cp's OEIS frontend

A022087 Fibonacci sequence beginning 0, 4.

0, 4, 4, 8, 12, 20, 32, 52, 84, 136, 220, 356, 576, 932, 1508, 2440, 3948, 6388, 10336, 16724, 27060, 43784, 70844, 114628, 185472, 300100, 485572, 785672, 1271244, 2056916, 3328160, 5385076, 8713236, 14098312, 22811548, 36909860, 59721408, 96631268

Offset: 0

N. J. A. Sloane

For n > 1, this sequence gives the number of binary strings of length n that do not contain 0000, 0101, 1010, or 1111 as contiguous substrings (see A230127). - Nathaniel Johnston, Oct 11 2013

A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 18.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Tanya Khovanova, Recursive Sequences
Index entries for linear recurrences with constant coefficients, signature (1,1).

Cf. A000045, A119457.
Cf. similar sequences listed in A258160.
Cf. sequences of the form m*Fibonacci listed in A022086.

[4*Fibonacci(n): n in [0..40]]; // Vincenzo Librandi, Oct 12 2013

a:= n-> (Matrix([[4,0]]). Matrix([[1,1],[1,0]])^n)[1,2]: seq(a(n), n=0..40); # Alois P. Heinz, Aug 17 2008

4*Fibonacci[Range[0,50]] (* Vladimir Joseph Stephan Orlovsky, Jul 22 2008 *)
Table[4 Fibonacci(n), {n, 0, 40}] (* Bruno Berselli, May 22 2015 *)
LinearRecurrence[{1,1},{0,4},40] (* Harvey P. Dale, Jul 31 2025 *)

a(n)=4*fibonacci(n) \\ Charles R Greathouse IV, Jun 05 2011

def A022087(n): return 4*fibonacci(n)
print([A022087(n) for n in range(41)]) # G. C. Greubel, Apr 12 2025

a(n) = 4*F(n) = F(n-2) + F(n) + F(n+2), where F = A000045.
a(n) = round( phi^n*(8*phi-4)/5 ) for n>2. - Thomas Baruchel, Sep 08 2004
a(n) = A119457(n+2,n-1) for n>1. - Reinhard Zumkeller, May 20 2006
G.f.: 4*x/(1-x-x^2). - Philippe Deléham, Nov 19 2008
a(n) = F(n+9) - 17*F(n+3), where F=A000045. - Manuel Valdivia, Dec 15 2009
G.f.: Q(0) -1, where Q(k) = 1 + x^2 + (4*k+5)*x - x*(4*k+1 + x)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Oct 07 2013
a(n) = Fibonacci(n+3) - Fibonacci(n-3), where Fibonacci(-3..-1) = 2,-1,1. - Bruno Berselli, May 22 2015

A229614 Number of binary strings of length n avoiding "squares" (that is, repeated blocks of the form xx) with |x| > 2.

Original entry on oeis.org

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

Jeffrey Shallit, Sep 26 2013

nonn

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

			For n = 6 there are 8 strings omitted, namely 000000, 001001, ..., 111111, so a(6) = 64 - 8 = 56.

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.

Cf. A230127, A230177, A230216.

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 *)

# 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

a(23)-a(36) from Nathaniel Johnston, Oct 10 2013

A230177 Number of binary strings of length n avoiding "squares" (that is, repeated blocks of the form xx) with |x| > 3.

Original entry on oeis.org

1, 2, 4, 8, 16, 32, 64, 128, 240, 464, 866, 1642, 3048, 5720, 10642, 19868, 36894, 68722, 127630, 237324, 440594, 818584, 1519802, 2822630, 5240262, 9730478, 18065252, 33542006, 62272196, 115616582, 214646190, 398507348, 739840164, 1373551484, 2550032248

Offset: 0

Nathaniel Johnston, Oct 11 2013

nonn

			a(8) = 256 - 16 = 240 because there are 256 binary strings of length 8, 16 of which contain a repeated block of length 4: 00000000, 00010001, 00100010, ..., 11111111.

R. C. Entringer, D. E. Jackson and J. A. Schatz, On nonrepetitive sequences, J. Combin. Theory Ser. A. 16 (1974), 159-164.
Nathaniel Johnston, C code for computing this sequence

Cf. A229614, A230127, A230216.

A230216 Number of binary strings of length n avoiding "squares" (that is, repeated blocks of the form xx) with |x| = 3.

Original entry on oeis.org

1, 2, 4, 8, 16, 32, 56, 104, 192, 352, 648, 1192, 2192, 4032, 7416, 13640, 25088, 46144, 84872, 156104, 287120, 528096, 971320, 1786536, 3285952, 6043808, 11116296, 20446056, 37606160, 69168512, 127220728, 233995400, 430384640, 791600768, 1455980808

Offset: 0

Nathaniel Johnston, Oct 11 2013

			For n = 6 there are 8 strings omitted, namely 000000, 001001, ..., 111111, so a(6) = 64-8 = 56.

Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (1,1,1).

Cf. A000073, A022087, A229614, A230127, A230177.

Vec((1 + x + x^2 + x^3 + 2*x^4 + 4*x^5) / (1 - x - x^2 - x^3) + O(x^40)) \\ Colin Barker, Aug 09 2019

a(n) = 8*A000073(n) for n >= 3.
From Colin Barker, Aug 09 2019: (Start)
G.f.: (1 + x + x^2 + x^3 + 2*x^4 + 4*x^5) / (1 - x - x^2 - x^3).
a(n) = a(n-1) + a(n-2) + a(n-3) for n>5.
(End)

cp's OEIS Frontend

A022087 Fibonacci sequence beginning 0, 4.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

SageMath

Formula

A229614 Number of binary strings of length n avoiding "squares" (that is, repeated blocks of the form xx) with |x| > 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Extensions

A230177 Number of binary strings of length n avoiding "squares" (that is, repeated blocks of the form xx) with |x| > 3.

Views

Author

Keywords

Examples

Links

Crossrefs

A230216 Number of binary strings of length n avoiding "squares" (that is, repeated blocks of the form xx) with |x| = 3.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula