Antonie Deza, Frantisek Franek and Mei Jiang
A Computational Framework for Determining Square-maximal Strings
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) < σ_{3}(33); that is, among all strings of length 33, no binary string achieves the maximum number of distinct primitively rooted squares. Noticeably, these computations reveal the unexpected existence of pairs (d,n) satisfying σ_{d+1}(n+2) – σ_{d}(n)>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. |
Download paper: | |||
PostScript | BibTeX reference |