A computational substantiation of the d-step approach to the number of distinct squares problem

作者：Deza Antoine; Franek Frantisek; Jiang Mei

来源：Discrete Applied Mathematics, 2016, 212: 81-87.

DOI：10.1016/j.dam.2016.04.025

• String
• Square
• Primitively rooted square
• Maximum number of distinct primitively rooted squares
• Parameterized approach
• (d, n - d) table

Motivated by the recent validation of the d-step approach for the number of runs problem, we investigate the largest possible number sigma(d)(n) of distinct primitively rooted squares over all strings of length n with exactly d distinct symbols. New properties of sigma(d)(n) are presented, and the notion of s-cover is introduced with an emphasis on the recursive computational determination of sigma(d)(n). In particular, we were able to determine all values of sigma(2)(n) for n <= 70, sigma(3)(n) for n <= 45 and sigma(4)(n) for n <= 38. These computations reveal the unexpected existence of pairs (d, n) satisfying sigma(d+1)(n + 2) - sigma(d)(n) > 1 such as (2, 33) and (2, 34), and of three consecutive equal values: sigma(2)(31) = sigma(2)(32) = sigma(2)(33). Noticeably, we show that among all strings of length 33, the maximum number of distinct primitively rooted squares cannot be achieved by a non-ternary string.

• 出版日期2016-10-30