Some Tribonacci Conjectures Jerey Shallit School of Computer Science

2025-05-03 0 0 269.42KB 11 页 10玖币

侵权投诉

Some Tribonacci Conjectures

Jeﬀrey Shallit

School of Computer Science

University of Waterloo

Waterloo, ON N2L 3G1

Canada

shallit@uwaterloo.ca

October 11, 2022

Abstract

In a recent talk of Robbert Fokkink, some conjectures related to the inﬁnite Tri-

bonacci word were stated by the speaker and the audience. In this note we show how

to prove (or disprove) the claims easily in a “purely mechanical” fashion, using the

Walnut theorem-prover.

1 Introduction

The Tribonacci sequence (Tn)n≥0satisﬁes the three-term recurrence relation

Tn=Tn−1+Tn−2+Tn−3

for n≥3, with initial values T0= 0, T1= 1, T2= 1; see [6,14]. It is sequence A000073 in

the On-Line Encyclopedia of Integer Sequences (OEIS); see [17]. The ﬁrst few values are as

follows:

n1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Tn1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136

Table 1: First few values of the Tribonacci sequence.

As is well-known, every non-negative integer Nhas a unique representation in the form

N=X

2≤i≤t

eiTi,

arXiv:2210.03996v1 [math.CO] 8 Oct 2022

where et= 1, ei∈ {0,1}, and eiei+1ei+2 6= 1 for i≥2 [3]. This representation is conven-

tionally written as a binary word (or string) (N)Twith the most signiﬁcant digit ﬁrst:

etet−1· · · e2. For example, (43)T= 110110. There is a related function [x]T=N, if

x=x1· · · xt∈ {0,1}∗and N=P1≤i≤txiTt+3−i.

Intimately connected with the Tribonacci sequence is the inﬁnite Tribonacci word

TR =t0t1t2· · · = 0102010 · · · ,

where tNis deﬁned to be the number of trailing 1’s in (N)T. This is a famous inﬁnite word

that has been extensively studied (e.g., [2,18,13,9,10]). It is sequence A080843 in the

OEIS.

The Tribonacci sequence and its relatives are intimately connected with a number of

combinatorial games [5]. In this note I will explain how one can rigorously prove properties

of these sequences “purely mechanically”, using various computational techniques involving

formal languages and automata. As an example of the method, we show how to prove

(or disprove!) some recent conjectures made in a talk by Robbert Fokkink. One of these

conjectures also appears just before Section 2 in [8].

We use the Walnut theorem-prover originally designed by Hamoon Mousavi [11]. This free

software is able to rigorously prove or disprove ﬁrst-order statements involving automatic

and synchronized sequences. For previous work with Walnut and the inﬁnite Tribonacci

word, see [12].

2 Automata

Our methods involve two classes of inﬁnite words, called Tribonacci-automatic and Tribonacci-

synchronized. For more about them, see [12,16].

An inﬁnite word xis said to be Tribonacci-automatic if there is a deterministic ﬁnite

automaton with output (DFAO) that, on input [N]T, the Tribonacci representation of N,

reaches a state with output x[N]. For more about automatic sequences, see [1].

An inﬁnite sequence of integers (yn)n≥0is said to be Tribonacci-synchronized if there is

a deterministic ﬁnite automaton (DFA) that, on input the Tribonacci representations of N

and xin parallel (the shorter one, if necessary, padded with leading zeros), accepts if and

only if x=yN. For more about synchronized sequences, see [15].

The Tribonacci word TR is Tribonacci-automatic, and is generated by the automaton in

Figure 1, where the output of the state numbered iis iitself.

Three examples of Tribonacci-synchronized sequences are the sequences (Dn)n≥0, (En)n≥0,

(Fn)n≥0deﬁned as follows:

Dn=|TR[0..n −1]|0

En=|TR[0..n −1]|1

Fn=|TR[0..n −1]|2.

Tribonacci automata for these sequences are given in [16,§10.12]. These are sequences

A276796,A276797, and A276798−1 in the OEIS, respectively.

Figure 1: Tribonacci automaton computing TR.

3 Two sequences related to combinatorial games

Our starting point is two sequences related to combinatorial games. These are sequences

A140100 and A140101 in the OEIS, from which we quote the deﬁnition more-or-less verbatim:

Deﬁnition 1. Start with X(0) = 0, Y(0) = 0, X(1) = 1, Y(1) = 2. For n > 1, choose

the least positive integers Y(n)> X(n) such that neither Y(n) nor X(n) appear in {Y(k) :

1≤k < n}or {X(k) : 1 ≤k < n}and such that Y(n)−X(n) does not appear in

{Y(k)−X(k) : 1 ≤k < n}or {Y(k) + X(k) : 1 ≤k < n}.

Table 2gives the ﬁrst few terms of these sequences.

n0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

X(n) 0 1 3 4 6 7 9 10 12 14 15 17 18 20 21 23

Y(n) 0 2 5 8 11 13 16 19 22 25 28 31 33 36 39 42

Table 2: First few values of the sequences (X(k))k≥0and (Y(k))k≥0.

These two sequences were apparently ﬁrst studied by Duchˆene and Rigo [5, Corollary 3.6]

in connection with a combinatorial game, and they established the close connection between

them and the inﬁnite Tribonacci word TR. Further properties were given in [4].

Because of the already-established connection with TR, one might conjecture that the

sequences X= (X(k))k≥0and Y= (Y(k))k≥0are both Tribonacci-synchronized. But how

can this be veriﬁed? There is no known method to take an arbitrary recursive description

of sequences, like the one given above in Deﬁnition 1, and turn it into automata computing

the sequences.

We do so in two steps. The ﬁrst is to use some heuristics to “guess” the automata for

Xand Y. We do that using (essentially) the classical Myhill-Nerode theorem, as described

below for an arbitrary sequence of natural numbers.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

SomeTribonacciConjecturesJereyShallitSchoolofComputerScienceUniversityofWaterlooWaterloo,ONN2L3G1Canadashallit@uwaterloo.caOctober11,2022AbstractInarecenttalkofRobbertFokkink,someconjecturesrelatedtotheinniteTri-bonacciwordwerestatedbythespeakerandtheaudience.Inthisnoteweshowhowtoprove(ordisprove)...

展开>> 收起<<

Some Tribonacci Conjectures Jerey Shallit School of Computer Science.pdf

共11页,预览3页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Some Tribonacci Conjectures Jerey Shallit School of Computer Science

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: