Periodic Words Connected With The Tribonacci Words Galyna BARABASH, Yaroslav KHOLYAVKA, Iryna TYTAR

ISSN 2078-3744. Âiñíèê Ëüâiâ. óí-òó. Ñåðiÿ ìåõ.-ìàò. 2016. Âèïóñê 81. Ñ.
58
Visnyk of the Lviv Univ. Series Mech. Math. 2016. Issue 81. P. 58
ÓÄÊ 512.624.5
PERIODIC WORDS CONNECTED WITH

THE TRIBONACCI WORDS
Galyna BARABASH, Yaroslav KHOLYAVKA, Iryna TYTAR
Ivan Franko National University of Lviv,

Universytetska Str., 1, Lviv, 79000
e-mails: galynabarabash71@gmail.com,
ya_khol@franko.lviv.ua,
iratytar1217@gmail.com
We introduce two families of periodic words (TLP-words of type 1 and

TLP-words of type 2) that are connected with the Tribonacci numbers
and Tribonacci words, respectively.
Key words: Tribonacci numbers, Tribonacci words.
1. Introduction.
The Tribonacci numbers Tn are dened by the recurrence relation Tn = Tn−1 +
Tn−2 + Tn−3 , for all integer n > 2, and with initial values T0 = 0, T1 = 0 and T2 = 1 (see,
e.g., [1, 2, 3]). Many properties of the Tribonacci numbers require the full ring structure
of the integers. However, generalizations to the ring Zm have been considered (see, e.g.,
[4]). The sequence Tn (mod m) is periodic and repeats by returning to its starting values
because there are only a nite number m3 of triples of terms possible, and the recurrence
of a triple results in recurrence of all the following terms.
In analogy to the denition of Tribonacci numbers, one denes the Tribonacci nite
words as the contatenation of the three previous terms tn = tn−1 tn−2 tn−3 , n > 2, with
initial values t0 = 0, t1 = 01 and t2 = 0102 and denes the innite Tribonacci word t,
t = lim tn (see [5]). It is the archetype of an Arnoux-Rauzy word (see, e.g., [6, 7]).
Using Tribonacci words, in the present article we shall introduce some new kinds of
the innite words, mainly TLP words, and investigate some of their properties.
For any notations not explicitly dened in this article we refer to [1, 6].
2. Tribonacci sequence modulo m.
The letter p is reserved to designate a prime and m may be arbitrary integer, m > 1.
Let Tn∗ (m), 0 6 Tn∗ (m) < m, denote the n-th member of the sequence of integers
Tn ≡ Tn−1 + Tn−2 + Tn−3 (mod m), for all integer n > 2, and with initial values T0 = 0,
T1 = 0 and T2 = 1 (T0∗ (m) = 0, T1∗ (m) = 0 and T2∗ (m) = 1). We reduce Tn modulo m
taking the least nonnegative residues, and let k(m) denote the length of the period of
⃝
c Barabash G., Kholyavka Ya., Tytar I., 2016
6 ISSN 2078-3744. Âiñíèê Ëüâiâ. óí-òó. Ñåðiÿ ìåõ.-ìàò. 2016. Âèïóñê 81
the repeating sequence Tn∗ (m). A few properties of the

( p function
) k(m) are in the following
theorem [4, 8]. Let p be an odd prime, p ̸= 11, and 11 denotes the Legendre symbol.
Theorem 1. In Zm the following hold:
1) Any
(p)Tribonacci sequence modulo m is periodic.
2) If 11 = 1, then k(p)|(p2 + p + 1) if x3 − x2 − x − 1 is irreducible mod p, otherwise
( p ) − 1).
k(p)|(p
3) If 11 = −1, then k(p)|(p2 − 1).
The results in Theorem 8 give upper bounds for k(p) but there are primes for which
k(p) is less than the given upper bound.
3. Tribonacci words.
Let t0 = 0, t1 = 01 and t2 = 0102. Now tn = tn−1 tn−2 tn−3 , n > 2, the contatenation
of the three previous terms. The successive initial nite Tribonacci words are:
t0 = 0, t1 = 01, t2 = 0102, t3 = 0102010, t4 = 0102010010201, . . . (1)
The innite Tribonacci word t is the limit t = limn→∞ tn . It is referenced A080843
in the On-line Encyclopedia of Integer Sequences [9]. The properties of the Tribonacci
innite words are of great interest in some elds of mathematics and its application such
as number theory, fractal geometry, formal language etc. See [5, 10, 11, 12, 13].
We denote as usual by |tn | the length (the number of symbols) of tn . The following
proposition summarizes basic properties of Tribonacci words [5].
Theorem 2. The innite Tribonacci word and the nite Tribonacci words satisfy the
following properties:
1) The words 11, 22 and 000 are not subwords of the innite Tribonacci word.
2) For all n > 0 let an be the last symbol of tn and k ≡ n (mod 3), k ∈ {0, 1, 2}. Then
we have an = k .
3) For all n > 0 |tn | = Tn+3 .
4. Periodic TLP words.
Let us start with the classical denition of periodicity of words over arbitrary
alphabet {a0 , a1 , a2 , . . . } (see [14]).
Denition 1. Let w = a0 a1 a2 . . . be an innite word. We say that w is
1) a periodic word if there exists a positive integer t such that ai = ai+t for all i > 0.
The smallest t satisfying the previous condition is called the period of w;
2) an eventually periodic word if there exist two positive integers t, s such that ai = ai+t ,
for all i > s;
3) an aperiodic word if it is not eventually periodic.
Theorem 3. The innite Tribonacci word is aperiodic.
This statement is proved in [10].
We consider the nite Tribonacci words tn (3) as numbers written in the ternary
numeral system and denote them by bn . Denote by dn the value of the number bn in
usual decimal numeration system. We write dn = bn meaning that dn and bn are writing
of the same number in dierent numeral systems.
PERIODIC WORDS CONNECTED WITH ...
ISSN 2078-3744. Âiñíèê Ëüâiâ. óí-òó. Ñåðiÿ ìåõ.-ìàò. 2016. Âèïóñê 81 7
Example 1.
t0 = 0, t1 = 01, t2 = 0102, t3 = 0102010, t4 = 0102010010201, . . . ,
b0 = 0, b1 = 1, b2 = 102, b3 = 102010, b4 = 102010010201, . . . ,
d0 = 0, d1 = 1, d2 = 11, d3 = 300, d4 = 218800, d5 = 38759787911, . . . .
Theorem 4. For any nite Tribonacci word tn we have
d0 = 0, d1 = 1, d2 = 11, dn = dn−1 3Tn+1 +Tn + dn−2 3Tn + dn−3 (n > 2). (2)
Proof. One can easily verify (4) for the rst few n : d3 = b3 = 102010 = 102000 +10 + 0 =
b2 33 +b1 31 +b0 = d2 33 +d1 31 +d0 , d4 = b4 = 102010010201 = 102010000000+10200+1 =
d3 36 + d2 32 + d1 . Equality (4) follows from Theorem 9 (statement 3)) and the equality
dn = bn = bn−1 0 | .{z
. . 0} +bn−2 0 . . 0} +bn−3 = dn−1 3Tn+1 +Tn + dn−2 3Tn + dn−3 .
| .{z
Tn+1 +Tn Tn
Let w0 (m) = 0 and for arbitrary integer n, n > 1, dn (m) = dn (mod m), 0 6
dn (m) < m, bn (m) is dn (m) in the ternary numeration system, wn (m) = wn−1 (m)bn (m).
Denote by w(m) the limit w(m) = limn→∞ wn (m).
Denition 2. We say that
1) wn (m) is a nite TLP word type 1 modulo m;
2) w(m) is an innite TLP word type 1 modulo m.
Theorem 5. The innite TLP word of type 1 w(p) is a periodic word.
Proof. The statement follows from (4) because there are only a nite number of dn (p)
and 3Tn (mod p) possible, and the recurrence of the rst few terms sequence dn (p) and
3Tn (mod p) gives recurrence of all subsequent terms.
Using Tribonacci words (3) we dene a periodic TLP word w∗ (m) (innite TLP
word type 2 by modulo m). As usual, we denote by ϵ the empty word. Let vn∗ (m) be the
last Tn+3
∗
(m) symbols of the word tn if Tn+3
∗
(m) ̸= 0, otherwise vn∗ (m) = ϵ.
Theorem 6. The word length |vn∗ (m)| coincides with Tn+3
∗
(m).
Proof. This is clear by construction of vn∗ (m) .
Since Tn∗ (m) is a periodic sequence with period k(m), the sequence |vn∗ (m)| is
periodic with the same period. Let w0∗ (m) = 0 and for arbitrary integer n, n > 1,
wn∗ (m) = wn−1
∗
(m)vn∗ (m). Denote by w∗ (m) the limit w∗ (m) = limn→∞ wn∗ (m).
Denition 3. We say that
1) wn∗ (m) is a nite TLP word of type 2 modulo m;
2) w∗ (m) is an innite TLP word of type 2 modulo m.
Theorem 7. The innite TLP word of type 2 w∗ (m) is a periodic word.
The Theorem 14 is a direct corollary of Theorem 9 (statement 2)) and Theorem 13.
References
1. Koshy T. Fibonacci and Lucas Numbers with Applications // Wiley-Interscience, New York,
2001.
8 ISSN 2078-3744. Âiñíèê Ëüâiâ. óí-òó. Ñåðiÿ ìåõ.-ìàò. 2016. Âèïóñê 81
2. Basu M. Tribonacci matrices and a new coding theory/M. Basu, M. Das// Discrete
Math. Algorithms Appl. Vol. 6 (1), 1450008(17 pages)(1450008-1 1450008-17),DOI:
10.1142/S1793830914500086.
3. Gerdes W. Generalized tribonacci numbers and their convergent sequences // Fibonacci
Quart.Vol.16. 1978. P.269275.
4. Waddill M. E. Some properties of a generalized Fibonacci sequence modulo m // The Fi-
bonacci Quart. Vol. 16. 1978, . 4. P.344353.
5. Rosema S. W. The Tribonacci substitution/S.W. Rosema, R. Tijdeman// Elect. J. of
Combin. Number Theory. Vol. 5(3). 2005, . A13 (electronic), http://www.integers-
ejcnt.org/vol5-3.html.
6. Glen A. Episturmian words/A. Glen, J. Justin// RAIRO-Theor. Inform. Appl. Vol. 43.
2009. P.403442.
7. Berstel J. Sturmian and episturmian words (a survey of some recent results)// Lecture Notes
in Computer Science. Vol. 4728. 2007.P.2347.
8. Vince A. Period of a linear recurrence// Acta Arithmetica. Vol. 39(4). 1981. P.303311.
9. Sloane N. J. A. The online Encyclopedia of Integer sequences// Published electronically at
http://oeis.org/A080843.
10. Mousavi H. Mechanical Proofs of Properties of the Tribonacci Word/H. Mousavi,
J. Shallit// arxiv:1407.5841.
11. Duchene E. A morphic approach to combinatorial games: the Tribonacci case /E. Duchene,
M. Rigo// RAIRO-Theor. Inf. Appl. Vol. 42 (2). 2008). P.375393.
12. Tan B. Some properties of the Tribonacci sequence/B. Tan, Z.-Y. Wen// European J.
Combin. Vol. 28. 2007. P.17031719.
13. Damanik D. Arnoux-Rauzy Subshifts/D. Damanik, L.Q. Zamboni // Linear Recurrences,
Powers and Palindromes, arxiv: math. CO/0208137v1.
14. Duval J.P. Recurrence and periodicity in innite words from local periods/J.P. Duval,
F. Mignosi, A. Restivo// Theoret. Comput. Sci. Vol. 262(1-2). 2001. P.269284.
doi:10.1016/S0304-3975(00)00204-8
Ñòàòòÿ: íàäiéøëà äî ðåäêîëåãi¨ 29.03.2016

ïðèéíÿòà äî äðóêó 08.06.2016
ÏÅÐIÎÄÈ×ÍI ÑËÎÂÀ, ÏÎÂ'ßÇÀÍI ÇI ÑËÎÂÀÌÈ

ÒÐIÁÎÍÀ××I
Ãàëèíà ÁÀÐÀÁÀØ, ßðîñëàâ ÕÎËßÂÊÀ, Iðèíà ÒÈÒÀÐ
Ëüâiâñüêèé íàöiîíàëüíèé óíiâåðñèòåò iìåíi Iâàíà Ôðàíêà,

âóë. Óíiâåðñèòåòñüêà, 1, Ëüâiâ, 79000
e-mails: galynabarabash71@gmail.com,
ya_khol@franko.lviv.ua,
iratytar1217@gmail.com
Îçíà÷åíî äâà âèäè ïåðiîäè÷íèõ ñëiâ (TLP-ñëîâà òèïó 1 òà TLP-ñëîâà

òèïó 2), ÿêi ïîâ'ÿçàíi ç ÷èñëàìè Òðiáîíà÷÷i òà ñëîâàìè Òðiáîíà÷÷i.
Êëþ÷îâi ñëîâà: ÷èñëà Òðiáîíà÷÷i, ñëîâà Òðiáîíà÷÷i.

Periodic Words Connected With The Tribonacci Words Galyna BARABASH, Yaroslav KHOLYAVKA, Iryna TYTAR

Uploaded by

Copyright:

Available Formats

Periodic Words Connected With The Tribonacci Words Galyna BARABASH, Yaroslav KHOLYAVKA, Iryna TYTAR

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Periodic Words Connected With The Tribonacci Words Galyna BARABASH, Yaroslav KHOLYAVKA, Iryna TYTAR

Uploaded by

Copyright:

Available Formats

ISSN 2078-3744. Âiñíèê Ëüâiâ. óí-òó. Ñåðiÿ ìåõ.-ìàò. 2016. Âèïóñê 81. Ñ.

PERIODIC WORDS CONNECTED WITH

Galyna BARABASH, Yaroslav KHOLYAVKA, Iryna TYTAR

Ivan Franko National University of Lviv,

We introduce two families of periodic words (TLP-words of type 1 and

the repeating sequence Tn∗ (m). A few properties of the

Ñòàòòÿ: íàäiéøëà äî ðåäêîëåãi¨ 29.03.2016

ÏÅÐIÎÄÈ×ÍI ÑËÎÂÀ, ÏÎÂ'ßÇÀÍI ÇI ÑËÎÂÀÌÈ

Ãàëèíà ÁÀÐÀÁÀØ, ßðîñëàâ ÕÎËßÂÊÀ, Iðèíà ÒÈÒÀÐ

Ëüâiâñüêèé íàöiîíàëüíèé óíiâåðñèòåò iìåíi Iâàíà Ôðàíêà,

Îçíà÷åíî äâà âèäè ïåðiîäè÷íèõ ñëiâ (TLP-ñëîâà òèïó 1 òà TLP-ñëîâà

You might also like