Name
Abstract | ||
|---|---|---|
All our words (sequences) are binary. A square is a subword of the form uu (concatenation). Two squares are distinct if they are of different shape, not just translates of each other. Otherwise they are repeated . Fibonacci words are defined by ƒ 0 = 0 , ƒ 1 = 1 , ƒ m = ƒ m − 1 ƒ m − 2 for m ⩾ 2. Let F m = ¦ƒ m ¦ . Then F 0 = 1, F 1 = 1, F m = F m − 1 + F m − 2 ( m ⩾ 2) are the Fibonacci numbers. Let D ( n ) and R ( n ) be the exact number of distinct and repeated squares, respectively, in ƒ n . We prove: D ( n ) = 2( F n − 2 − 1) ( n ⩾ 5), which implies, asymptotically, D ( n ) = 2(2 − ϑ ) F n + o (1)(2(2 − ϑ ) ≈ 0.7639), where ϑ is the golden section. We also prove: R(n) = 4 5 nF n − 2 5 (n + 6)F n − 1 − F n − 2 + n + 1 (n ⩾ 3) . This yields R(n) = 2 5 (3 − ϑ)nF n + O(F n ) = (2(3 − ϑ) (5 log 2 ϑ))F n log 2 F n + O(F n )(2(3 − ϑ) (5 log 2 ϑ) ≈ 0.7962) . |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1016/S0304-3975(98)00252-7 | Theoretical Computer Science |
Keywords | DocType | Volume |
Repetitions,Exact Number,form uu,Fibonacci words,different shape,exact number,Fibonacci Words,Fibonacci word,Squares | Journal | 218 |
Issue | ISSN | Citations |
1 | Theoretical Computer Science | 14 |
PageRank | References | Authors |
1.66 | 2 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Aviezri S. Fraenkel | 1 | 559 | 164.51 |
| Jamie Simpson | 2 | 164 | 21.41 |