A Computational Framework for Determining Square-maximal Strings.
Antoine Deza, František Franěk, Mei Jiang · 2012
Abstract. We investigate the function σd(n) = max{s(x) | x is a (d, n)-string}, where s(x) denotes the number of distinct primitively rooted squares in a string x and (d, n)-string denotes a string of length n with exactly d distinct symbols. New properties of the σd(n) function are presented. The notion of s-cover is presented and discussed with emphasis on the recursive computational determination of σd(n). In particular, we were able to determine all values of σ2(n) for n ≤ 53 and σ3(n) for n ≤ 42 and to point out that σ2(33) 1 such as (2,33) and (2,34), and of three consecutive equal values: σ2(31) = σ2(32) = σ2(33). In addition we show that σ2(n) ≤ 2n − 66 for n ≥ 53.