On the maximum number of distinct factors of a binary string (Q2366959)

If \(x,y\), and \(z\) denote three strings of 0's and 1's, then \(y\) is called a factor of the string \(xyz\) (obtained by concatenation). The number of distinct factors of a string \(w\) is denoted by \(d(w)\). So \(d(10110)=12\). Two theorems are proved. The first is the (easy) result: Theorem. If \(| w|=n\), then \(d(w)\leq{n-k+1\choose 2}+2^{k+1}-1\), where \(k\) is the unique integer such that \(2^ k+k-1\leq n<2^{k+1}+k\). The main result is the fact that equality is attained for all \(n\). The proof depends on a lemma stating that, for \(2^ k\leq i\leq 2^{k+1}\), the De Bruijn graph \(B_ k\) (on \(2^ k\) vertices) contains a closed path of length \(i\) (a misprint in the paper states \(k)\) that visits every vertex at least once. The proof of the lemma is based on a result of \textit{M. Yoeli} [Binary ring sequences, Am. Math. Mon. 69, 852-855 (1962; Zbl 0107.249)] which states that \(B_ k\) contains a cycle of length \(i\) for any \(i\) such that \(0<i\leq 2^ k\) and also a closed path of length \(i+2^ k\).