The Square Trees in the Tribonacci Sequence

2016/05/15 by Yuke Huang, Zhiying Wen, Huang, Yuke +2
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Algorithms and Data Compression #math.DS #msc:11B85 #msc:68Q45 #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1605.04505

6 pages

arxiv created 2016/05/15 · arxiv updated 2016/05/17

Abstract

The Tribonacci sequence \mathbbT is the fixed point of the substitution σ(a,b,c)=(ab,ac,a). In this note, we get the explicit expressions of all squares, and then establish the tree structure of the positions of repeated squares in \mathbbT, called square trees. Using the square trees, we give a fast algorithm for counting the number of repeated squares in \mathbbT[1,n] for all n, where \mathbbT[1,n] is the prefix of \mathbbT of length n. Moreover we get explicit expressions for some special n such as n=t_m (the Tribonacci number) etc.

Related

• The numbers of distinct and repeated squares and cubes in the Tribonacci sequence
• The Numbers of Distinct Squares and Cubes in the Tribonacci Sequence
• The numbers of powers in the Tribonacci sequence
• The number of distinct and repeated squares and cubes in the Fibonacci sequence
• Mechanical Proofs of Properties of the Tribonacci Word