The appearance function for paper-folding words Rob Burns 27th October 2022

2025-05-06 0 0 782.44KB 11 页 10玖币

侵权投诉

The appearance function for paper-folding words

Rob Burns

27th October 2022

Abstract

We provide a complete characterisation of the appearance function for paper-

folding sequences for factors of any length. We make use of the software package

Walnut to establish these results.

1 Introduction

The regular paper-folding sequence begins 1, 1, -1, 1, 1, -1, -1, 1, . . . . It is derived

from the hills and valleys created when a piece of paper is folded length-wise multiple

times. In the limit, it consists of an inﬁnite sequence of 1’s and −1’s, in which a

1corresponds to a hill and a −1to a valley in the unfolded paper. This sequence,

with −1’s replaced by 0’s, appears as sequence A014577 in the On-Line Encyclopedia

of Integer Sequences (OEIS).[1] In a more general form, introduced by Davis and

Knuth,[2] a paper-folding sequence is derived from an inﬁnite folding instruction set.

This set of instructions also consists of an inﬁnite sequence of 1’s and −1’s and

determines the way in which the paper is folded. The regular paper-folding sequence

is produced by an instruction set consisting of an inﬁnite sequence of 1’s.

In this paper, we study the appearance function of the paper-folding sequences. We

show that, when n≥7, the appearance function is determined in a simple way by

the folding instruction set. The connection between the folding instructions and the

appearance function for smaller values of nis not quite as simple, but can still be

described.

We make use of the software package Walnut. Hamoon Mousavi, who wrote the

program, has provided an introductory article [7]. Papers that have used Walnut

include [8], [11], [9], [6], [4]. Further resources related to Walnut can be found at

Jeﬀrey Shallit’s page.

The free open-source mathematics software system SageMath [12] was used to check

some of the calculations.

arXiv:2210.14719v1 [math.NT] 22 Oct 2022

2 Background and notation

Let wbe an inﬁnite word. The ﬁrst element of wis denoted by w[1], the second

element by w[2] etc.. A sub-word of wis a continuous set of elements contained

within w. The sub-word w[i], w[i+ 1], w[i+2], . . . , w[j]will be abbreviated to w[i:j].

A ﬁnite word is called a factor of wif it appears as a sub-word of w. The length

kpreﬁx of wis the length ksub-word of wstarting with the element w[1], i.e. the

subword w[1 : k].

The appearance function of w, denoted Aw(n), is deﬁned to be the least integer k

such that a copy of each length nfactor of wis contained in the preﬁx w[1 : k]. For

convenience we will use a related function which we call Sw(n).Sw(n)is deﬁned to

be the least integer k such that a copy of each length nfactor of wstarts somewhere

within the preﬁx w[1 : k]. The two functions are connected by the equation Aw(n) =

Sw(n) + n−1.

The set of folding instructions associated with a paper-folding sequence will be de-

noted by f= (f0, f1, f2, . . . ). The paper-folding sequence associated to the folding

instructions fwill be denoted by Pf=Pf[1], Pf[2], . . . . The appearance function of

Pfwill be abbreviated to Afand SPfwill be abbreviated to Sf.

Dekking, Mendés France and van der Poorten [3] showed that the value of Pf[k]can

be written in terms of fin a fairly simple way. If k= 2s·rwhere ris odd, then

Pf[k] = (fs,if r≡1 (mod 4)

−fs,if r≡3 (mod 4) (1)

Schaeﬀer [10] observed that equation (1) leads to a 5-state deterministic ﬁnite au-

tomaton that takes, as input the base-2 expansion of an integer kin parallel with the

folding instructions fand outputs Pf[k]. The automaton outputs the correct value of

Pf[k]provided that enough folding instructions have been read in. In particular, more

than log2(k)folding instructions must be included in the input. The Walnut software

package includes this automaton and can be used to investigate its behaviour.

For integers n, deﬁne the function φ(n)to be the least integer rsuch that r≥nand

ris a power of 2. So, if 2k−1< n ≤2k, then φ(n)=2k. An alternative deﬁnition is

that

φ(n)=2k,where k=dlog2(n)e.

Schaeﬀer [10] showed that, when n≥3:

max

fSf(n)=6·φ(n).(2)

Goč et al. [5] showed that when n≥7,

min

fSf(n)=4·φ(n).(3)

3 Formula for Sfand Af

We begin this section with some Walnut commands. Walnut includes an automaton

which takes as parallel input a folding instruction set fand the base-2 representation

of an integer k, written in least signiﬁcant digit (lsd) ﬁrst order, and outputs the

value of Pf[k]. The Walnut representation of Pf[k]is P F [f][k]. We now introduce

some Walnut formulae which will be useful. Firstly we deﬁne the automaton pffaceq

which takes as parallel input the folding instruction set fand three integers i,jand

n, written in base-2 lsd format. The resulting automaton accepts the input if and

only if the length nsubwords of Pfstarting at indices iand jare identical. Since it

has 153 states, it cannot be displayed here.

def pffaceq "?lsd_2 Ak (k < n) => PF[f][i+k] = PF[f][j+k]":

The following code creates an automaton related to the function φwhich was deﬁned

in section 2. The automaton takes two integers xand yas input, written in base-2

lsd form. It accepts the input if xis a power of 2and φ(y) = x. We use the name

pfphi for this automaton. It is pictured in ﬁgure 1.

reg power2 lsd_2 "0*10*":

def pfphi "?lsd_2 $power2(x) & (x >= y) & x < 2*y":

Figure 1: Automaton pfphi.

We now create an automaton pfapp which takes as parallel input a folding instruction

set fand two integers iand n, written in base-2 lsd format. The resulting automaton

accepts the input if and only if the length nfactor of Pfstarting at index idoes not

appear earlier within Pf. This automaton has 121 states.

def pfapp "?lsd_2 (Aj (j<i) => (Et t<n & PF[f][i+t] != PF[f][j+t]))":

We next establish some preliminary results.

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

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

10 玖币 0人已下载

立即下载

摘要：

Theappearancefunctionforpaper-foldingwordsRobBurns27thOctober2022AbstractWeprovideacompletecharacterisationoftheappearancefunctionforpaper-foldingsequencesforfactorsofanylength.WemakeuseofthesoftwarepackageWalnuttoestablishtheseresults.1IntroductionTheregularpaper-foldingsequencebegins1,1,-1,1,1,-1,...

展开>> 收起<<

The appearance function for paper-folding words Rob Burns 27th October 2022.pdf

共11页,预览3页

还剩页未读，继续阅读

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

The appearance function for paper-folding words Rob Burns 27th October 2022

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: