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

详细信息    查看全文

• 作者：Antoine Deza ^{deza@mcmaster.ca" class="auth_mail" title="E-mail the corresponding author} ; Frantisek Franek ; ^{franek@mcmaster.ca" class="auth_mail" title="E-mail the corresponding author} ; Mei Jiang ^{jiangm5@mcmaster.ca" class="auth_mail" title="E-mail the corresponding author}
• 关键词：String ; Square ; Primitively rooted square ; Maximum number of distinct primitively rooted squares ; Parameterized approach ; (d ; n&minus ; dd ; n&minus ; d) table
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：30 October 2016
• 年：2016
• 卷：212
• 期：Complete
• 页码：81-87
• 全文大小：432 K

文摘

Motivated by the recent validation of the d$d$-step approach for the number of runs problem, we investigate the largest possible number σ_d(n)${\sigma }_d\left(n\right)$ of distinct primitively rooted squares over all strings of length n$n$ with exactly d$d$ distinct symbols. New properties of σ_d(n)${\sigma }_d\left(n\right)$ are presented, and the notion of s$s$-cover is introduced with an emphasis on the recursive computational determination of σ_d(n)${\sigma }_d\left(n\right)$. In particular, we were able to determine all values of σ₂(n)${\sigma }_2\left(n\right)$ for n≤70$n\le 70$, σ₃(n)${\sigma }_3\left(n\right)$ for n≤45$n\le 45$ and σ₄(n)${\sigma }_4\left(n\right)$ for n≤38$n\le 38$. These computations reveal the unexpected existence of pairs (d,n)$(d,n)$ satisfying σ_d+1(n+2)−σ_d(n)>1${\sigma }_{d+1}(n+2)-{\sigma }_d\left(n\right)>1$ such as (2, 33) and (2, 34), and of three consecutive equal values: ca019ef2" title="Click to view the MathML source">σ₂(31)=σ₂(32)=σ₂(33)${\sigma }_2\left(31\right)={\sigma }_2\left(32\right)={\sigma }_2\left(33\right)$. 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.