The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A248425 Number of "squares" (repeated identical blocks) in the n-th Fibonacci word. 0
 0, 0, 0, 0, 1, 4, 11, 26, 57, 118, 235, 454, 857, 1588, 2899, 5228, 9333, 16520, 29031, 50702, 88077, 152290, 262239, 449930, 769461, 1312104, 2231591, 3786456, 6410857, 10832908, 18272195, 30769154, 51733857, 86859598, 145642579, 243907918, 408005393, 681773980, 1138094971, 1898045252, 3162632157, 5265345680 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,6 COMMENTS Here the Fibonacci words are given by X_0 = 0, X_1 = 1, and X_n = X_{n-1} X_{n-2} where juxtaposition means concatenation. LINKS A. S. Fraenkel and J. Simpson, The exact number of squares in Fibonacci words, Theoret. Comput. Sci. 218 (1999), 95-106. Note:  the formula given there has a small error, which has been corrected below. A. S. Fraenkel and J. Simpson, Corrigendum to “The exact number of squares in Fibonacci words”, Theoret. Comput. Sci. 218 (1999), 95-106. FORMULA a(n) = (4/5)nF(n+1) - (2/5)(n+6)F(n) - 4F(n-1) + n + 1 (for n >= 3). Empirical g.f.: x^5*(x^4-x^2+1) / ((x-1)^2*(x^2+x-1)^2). - Colin Barker, Oct 07 2014 EXAMPLE The 5th Fibonacci word is 10110101, which has the following four squares: 11 starting at position 3, 1010 at position 4, 0101 at position 5, and 101101 at position 1. CROSSREFS Cf. A061107. Sequence in context: A027660 A002940 A030196 * A130103 A000295 A125128 Adjacent sequences:  A248422 A248423 A248424 * A248426 A248427 A248428 KEYWORD nonn AUTHOR Jeffrey Shallit, Oct 06 2014 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified March 31 03:48 EDT 2020. Contains 333136 sequences. (Running on oeis4.)