How Many Squares Must a Binary Sequence Contain?

Aviezri S. Fraenkel, R. Jamie Simpson

Source record

Source: Crossref

Published: Dec 11, 1994

DOI: 10.37236/1196

Open original source ↗

Source 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.

Evidence graph

No public relationships recorded yet.

Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.

How Many Squares Must a Binary Sequence Contain? — Mathematical Frontier Network