How Many Squares Must a Binary Sequence Contain?

  • Aviezri S. Fraenkel
  • R. Jamie Simpson
DOI: https://doi.org/10.37236/1196

Abstract

Let $g(n)$ be the length of a longest binary string containing at most $n$ distinct squares (two identical adjacent substrings). Then $g(0)=3$ (010 is such a string), $g(1)=7$ (0001000) and $g(2)=18$ (010011000111001101). How does the sequence $\{g(n)\}$ behave? We give a complete answer.

Published
1994-12-11
Issue
Volume 2 (1995)
Article Number
R2