#A104 INTEGERS 25 (2025)
DECOMPOSITION OF BEATTY AND COMPLEMENTARY
SEQUENCES
Ge emias Polanco
Depa men o Ma hema ics, Smi h College, No hamp on, Massachuse s
Recei ed: 7/7/21, Re ised: 1/13/25, Accep ed: 10/29/25, Published: 11/25/25
Abs ac
In his pape , we exp ess he di e ence o wo complemen a y Bea y sequences as
he sum o wo o he closely ela ed Bea y sequences. In he p ocess, we in oduce
a new algo i hm ha gene alizes he well-known Minimum Excluded algo i hm and
p o ides a me hod o combina o ially gene a e any pai o complemen a y Bea y
sequences in a na u al way.
1. In oduc ion
Wy ho [31] p o ed he o mula
nϕ2−[nϕ]=n, (1)
whe e ϕis he golden a io. He e, [x] deno es he la ges in ege no exceeding x.
La e , o he au ho s (see, o ins ance, [15] and [19]) used he o mula
nα2−[nβ]= n,
wi h α=2− +√ 2+4
2, and βsa is ying α−1+β−1= 1, o gene alize Wy ho ’s game.
O he gene aliza ions ha e been made co e ing Bea y sequences pa ame e ized by
limi ed amilies o i a ional numbe s. We ob ain a gene aliza ion o Iden i y (1)
o all complemen a y sequences and gi e a combina o ial in e p e a ion o he
co esponding quan i y on he igh -hand side. Fo example,
"n3 + √3
2#−hn√3i="n√3−1
2#+hn(2 −√3)i+ 1.
In pa icula , we p o e Theo ems 2, 3 and 4, which oge he imply ha Equa-
ion (1) gene alizes o any pai o complemen a y Bea y sequences Aand Bwi h
i a ional slopes β > 2 and αas ollows:
[nβ]−[nα] = [n(β−2)] + [n(2 −α)] + 1.(2)
DOI: 10.5281/zenodo.17711544
INTEGERS: 25 (2025) 2
Mo eo e , as we shall p o e la e , he wo quan i ies in he b acke s on he
igh -hand side o he equali y coun he numbe o in ege s ha belong o Aand
B, espec i ely, among hose in ege s lying in he hal -open in e al [an, bn). Inci-
den ally, he i le o his pape alludes o Equa ion (2), i s in e p e a ion, and i s
gene aliza ion in Theo ems 2 h ough Theo em 7.
We s a by se ing some use ul no a ion. We will call Aand Bcomplemen a y
se s o na u al numbe s i A∩B=∅and A∪B=N. Fo any mul ise Xo
in ege s ha is bounded below, we numbe he elemen s (wi h mul iplici y) o X
as x1≤x2≤..., linking in his way indexed lowe case le e s ( he elemen s in
non-dec easing o de ) and he uppe case le e s ( he se ). We use se sub ac ion
and addi ion o deno e he e m-wise ope a ions:
X±Y={xn±yn:n∈N}.
A se whose e ms a e gi en by bn= [nβ] o some β > 0 is called a Bea y sequence.
We emind he eade o Bea y’s Theo em (see, o ins ance, [28]):
Theo em 1 (Bea y-Rayleigh, [8]).The se s Aand Bgi en by an= [nα]and
bn= [nβ], espec i ely, a e complemen a y se s o na u al numbe s i and only i α
is a posi i e i a ional and 1
α+1
β= 1.
The es o he pape is ou lined as ollows. We end his sec ion by highligh -
ing he impo ance o he subjec . In Sec ion 2 we s a e he Minimum Excluded
(MEX) algo i hm, amilia om he heo y o impa ial games, and gene alize i
by in oducing he no el Minimum Excluded wi h Skipping (MES) algo i hm. The
la e will la e link o ou combina o ial in e p e a ion. In Sec ion 3 we s a e and
p o e Theo ems 2, 3, and 4, he main esul s o he pape , and explo e u he
implica ions o he MES algo i hm, such as i s combina o ial in e p e a ion.
To p o e he esul s o his pape , we use combina o ial a gumen s, basic analy ic
echniques, and s anda d p ope ies o Bea y and S u mian sequences. Fo α > 1,
he S u mian sequence wi h slope 1/α encodes he Bea y sequence wi h slope α[4,
Lemma 9.1.3]. The e is also a co esponding ela ionship be ween non-homogeneous
Bea y and S u mian sequences [11, Lemma 1]. S u mian sequences in gene al and
Bea y sequences in pa icula , a e he ocus o a g owing amoun o esea ch,
as hey play a ole in a ious ields o ma hema ics [25], biology [17], music [24],
compu e science [13], and physics (see also [4], [22], [9], [10] and he e e ences
he ein). The name “S u mian” was in oduced by Hendlund and Mo se in hei
in luen ial wo k in he 1940s [21]; howe e , he his o y o hese sequences da es back
o 1772 when Be noulli III wo ked wi h wha is now known as a non-homogeneous
S u mian sequence (see [4]). In pu e ma hema ics, S u mian and Bea y sequences
ha e been s udied in ela ion o dynamical sys ems [21], ixed-poin mo phisms
[28], loga i hm o i a ional numbe s [26], p ime numbe s [7], algeb aic numbe s
[16], a i hme ic unc ions [2], p imi i e oo s, di iso unc ions, cha ac e sums,
INTEGERS: 25 (2025) 3
among o he s (see [1], [3], [6], [18], [25], [27], [29], and he e e ences he ein). Mo e
ecen ly, he second and hi d momen s o Bea y sequences and hei squa es ha e
also been s udied [23]. We s udy di e ences o Bea y sequences in ela ion o
he well-known MEX algo i hm ha is widely used in combina o ial game heo y,
colo ing algo i hms, and elsewhe e (see, o ins ance, [5], [12], [14], [20], and [30]).
2. Miminum Excluded and Minimum Excluded wi h Skipping
Algo i hms
In his sec ion, we p esen he well-known MEX algo i hm, in oduce he MES
algo i hm as i s gene aliza ion, as well as de ini ions and no a ions necessa y o
s a e and p o e Theo em 2. We s a wi h he ollowing de ini ion.
De ini ion 1. Gi en a se S⊂N, he mex o he se Sis de ined as mex(S) :=
min(Sc∩N), ha is, mex(S) is he minimum na u al numbe ha is no in S.
I is well known ha complemen a y sequences can be gene a ed using he mex
ule abo e (see, o ins ance, [16]). We call his p ocess he MEX algo i hm and
de ine i igh below. Th oughou he emainde o he pape , i Ais a sequence,
we use An o deno e he se An={ak:k≤n}.
De ini ion 2. Gi en an inpu sequence H, he Minimum Excluded Algo i hm is
he ollowing se o algo i hmic ecu sions.
•STEP 1: Take a1= 1.
•STEP 2: I n≥2, ake an= mex{ai, bi|i < n}= mex(An−1∪Bn−1).
•STEP 3: I n≥1, ake bn=an+hn.
•STEP 4: Repea s eps 2 and 3.
To ou knowledge, he i s documen ed use o he MEX algo i hm o gene a e
Bea y sequences combina o ially was by B i ish ma hema ician Willem A. Wy ho
in 1907 [31]. He did so wi h he pu pose o p esen ing a modi ica ion o he combi-
na o ial game Nim. He showed ha he winning posi ions o his game we e gi en
by he Bea y pai s (an, bn), de ined by he golden a io. In ou con ex , his
co esponds o aking hn=nin he MEX algo i hm abo e. Fo he pu pose o
illus a ion, le us un he i s ew ounds o he algo i hm wi h hn=n. Applying
STEPS 1, 2, and 3, we ge a1= 1 and b1=an+n= 1 + 1 = 2, so A1={1}
and B1={2}. Applying STEP 4, we i s ob ain a2= mex(A1∪B1) = 3 and
b2=an+n= 3 + 2 = 5, so ha A2={1,3}and B2={2,5}. I we ollow his
p ocess, he i s i e i e a ions gi e Table 1.
INTEGERS: 25 (2025) 4
mex(An−1∪Bn−1)bn=an+n An={ak:k≤n}Bn={bk:k≤n}
a1= 1 b1= 1 + 1 = 2 A1={1}B1={2}
a2= 3 b2= 3 + 2 = 5 A2={1,3}B2={2,5}
a3= 4 b3= 4 + 3 = 7 A3={1,3,4}B3={2,5,7}
a4= 6 b4= 6 + 4 = 10 A4={1,3,4,6}B4={2,5,7,10}
a5= 8 b5= 8 + 5 = 13 A5={1,3,4,6,8}B5={2,5,7, . . .}
Table 1: Fi s ew i e a ions o he MEX algo i hm
No e ha he se Anag ees wi h he i s n e ms o he sequence Agi en by
he golden a io. Simila ly, Bnag ees wi h he i s n e ms o i s complemen a y
Bea y sequence.
We now gene alize he MEX algo i hm by modi ying STEP 3, and call his
gene aliza ion he Minimum Excluded wi h Skipping algo i hm. To ind bn, we
choose he minimum excluded elemen a e skipping a numbe o in ege s. We
base he MES algo i hm on he ollowing gene aliza ions o De ini ion 1.
De ini ion 3. Gi en a se o in ege s Aand a non-nega i e in ege k, we de ine a
unc ion deno ed by mexk(A) ha selec s he (k+ 1)s minimum excluded posi i e
in ege om he se A. In o he wo ds, o ind mexk(A), we skip he i s kexcluded
in ege s om Aand selec he nex excluded in ege .
We now de ine he MES algo i hm.
De ini ion 4. Gi en a sequence o non-nega i e in ege s C={cn}∞
n=1, he Min-
imun Excluded wi h Skipping Algo i hm is gi en by he ollowing se o algo i hmic
ecu sions.
•STEP 1: Se a1= 1, A1={a1}={1}, and B0=∅( he emp y se ).
•STEP 2: Fo n≥2, se an= mex(An∪Bn).
•STEP 3: Fo n≥1, se bn= mexcn(An∪Bn−1), ha is, skip he i s cn
excluded posi i e in ege s and selec he nex excluded in ege om his union.
•STEP 4: Repea s eps 2 and 3.
Example 1. We use he sequence C={0,1,1,2,3,3,4,4,5,6,6,7,8,8, . . . } o il-
lus a e he MES algo i hm. S a ing wi h B0=∅, he i s i e a ion gi es a1= 1,
and b1= mexc1(A1∪B0) = mex0{1}= 2. So, A1={1}and B1={2}. The second
i e a ion gi es a2= mex(A1∪B1) = 3 and b2= mexc2(A2∪B1) = mex1{1,2,3}= 5,
as 5 is he second minimum excluded in ege a e skipping he i s excluded in ege
4. Con inuing his p ocess, subsequen i e a ions a e shown in Table 2.
INTEGERS: 25 (2025) 5
anbnAn={ak:k≤n}Bn={bk:k≤n}
a1= 1 b1= mex0= 2 A1={1}B1={2}
a2= 3 b2= mex1= 5 A2={1,3}B2={2,5}
a3= 4 b3= mex1= 7 A3={1,3,4}B3={2,5,7}
a4= 6 b4= mex2= 10 A4={1,3,4,6}B4={2,5,7,10}
a5= 8 b5= mex3= 13 A5={1,3,4,6,8}B5={2,5,7,10,13}
a6= 9 b6= mex3= 15 A6={1,3,4,6,8,9}B6={2,5,7,10,13,15}
a7= 11 b7= mex4= 18 A7={1,3,4,6,8,9,11}B7={2,5,7,10,13, . . .}
Table 2: MES algo i hm: an= mex(An−1∪Bn−1) and bn= mexcn(An∪Bn−1).
n h ABC
1) 1 2 0
2) 1
3) 1
4) 2
Table 3: MES S eps.
n h ABC
1) 1 2 0
2) 3 5 1
3) 4 7 1
4) 2
5) 3
6) 3
7) 4
8) 4
9) 5
Table 4: MES S eps.
n h A B C
1) 1 2 0
2) 3 5 1
3) 4 7 1
4) 6 10 2
5) 8 13 3
6) 9 15 3
7) 11 18 4
8) 12 20 4
9) 14 23 5
10) 16 26 6
11) 17 28 6
12) 19 31 7
Table 5: MES S eps.
Rema k 1. Because o how i is used in STEP 3 o he MES de ini ion abo e,
we call C he skipping sequence o he MES algo i hm. A e a close look a he
esul ing Table 2, one can see ha he sequence Cused in he MES abo e can be
de ined induc i ely by he ule: a posi i e in ege ha has been assigned by he
algo i hm o Aappea s wice in C, o he wise i appea s once. In o he wo ds, he
algo i hm can be gene a ed wi hou explici ly lis ing he sequence C, only using
he ini ial alue c0= 0, and he induc i e ule jus s a ed. Tables 3, 4, and 5
illus a e how Cis gene a ed induc i ely in his way. La e we expand on his,
showing ha he esul ing sequences om he MES algo i hm (Sequences A and B)
a e he complemen a y pai gi en by he golden a io. This is Theo em 2 (4a).
We need he ollowing de ini ion.
De ini ion 5. The so join o wo in ege sequences Aand B, deno ed by A⋆B,
is he union wi h epe i ion o he o de ed elemen s o hese wo sequences.
We use A2 o he so join o Awi h i sel , ha is, A2=A ⋆ A, and we ep esen
INTEGERS: 25 (2025) 6
he so join o kcopies o Awi h i sel by Ak. Finally, we use N0 o deno e he
non-nega i e in ege s. Fo ins ance, i A ep esen s he e en na u al numbe s, hen
A⋆N2
0={0,0,1,1,2,2,2,3,3,4,4,4,5,5, . . .}, because he numbe s 2,4,6, . . . epea
h ee imes while he o he s only epea wice.
We need wo mo e de ini ions be o e p o ing Theo em 2. Pa (4) o Theo em
2 men ions he case when a sequence Cis gi en by he so join C=D ⋆ Nk−1
0in
he MES algo i hm. In his case, he sequence Cis comple ely de e mined by he
sequence D. Since Cde ines he MES algo i hm (and Dde ines C), i e ec i ely
ollows ha Dde ines he MES algo i hm. We eco d his in he ollowing de ini ion.
De ini ion 6. I he e is an inc easing sequence o na u al numbe s Dsuch ha
he sequence Co he MES algo i hm is gi en by C=D ⋆ Nk−1
0, we call D he
de ining sequence o he MES algo i hm.
We also use he ollowing de ini ion.
De ini ion 7. Fo n≥1, conside he (possibly emp y) hal -open in ege in e al
(an, bn−1], and le nbe he ca dinali y o he in e sec ion o his in e al wi h Bn−1,
i.e., n= #{b|b∈(an, bn−1] and b∈Bn−1}. We de ine he auxilia y sequence R
by R:= { n}∞
n=1.
Rema k 2. Consis en wi h he use o Anand Bn, we use he con en ion Rn:=
{ k:k≤n}. We also no e he e o u u e e e ence ha he sequence cnis a
coun ing sequence o some elemen s o he sequence A. Speci ically we ha e
cn= #{a∈A|an< a < bn}.
This o mula ollows because once an in ege is skipped when selec ing bn, ha
in ege will ne e be selec ed by he sequence Bin u u e s eps, hus ha elemen
will be picked up by A. This is ue whene e cnis non-dec easing.
3. S a emen and P oo o he Main Theo ems
The main esul s o his pape a e Theo ems 2, 3, and 4, which oge he p o ide a
comple e pic u e o he MES algo i hm and i s ela ion o decomposing he di e -
ence o wo Bea y sequences as he sum o wo o he sequences. Theo em 2, pa
(a), exp esses he di e ence o wo Bea y sequences as he sum o wo gene alized
Bea y sequences, yielding Fo mula (3). Pa (b) o his heo em p o ides an in e -
p e a ion o his o mula: he MES algo i hm. In o he wo ds, i s a es how we can
compu e anand bn om Equa ion (3), using he MES algo i hm.
Theo ems 3 and 4 s a e ha i he esul ing complemen a y sequences in he
MES algo i hm, Aand B, a e Bea y sequences, hen he skipping sequence Chas
INTEGERS: 25 (2025) 7
slope β−2, and he coun ing sequence Rhas slope 2 −α, whe e αand βa e he
slopes o he sequences Aand B, espec i ely.
Finally, Theo em 7 s a es necessa y and su icien condi ions o he ou pu se-
quences Aand B o be Bea y sequences in he MES algo i hm. I also ela es
hei slopes o he slope o he inpu sequence D, and ea s some pa icula cases
o in e es .
We now s a e and p o e Theo em 2.
Theo em 2. Suppose ha Aand Ba e any pai o complemen a y sequences. We
ha e he ollowing s a emen s.
(a) The sequence o med by he di e ence A−B, e m by e m, can always be
decomposed in e ms o he sum o wo o he sequences Cand Ras ollows:
bn−an=cn+ n+ 1,(3)
whe e cncoun s he numbe o in ege s s ic ly be ween anand bn ha belong
o he sequence A, and ncoun s he numbe o in ege s s ic ly be ween an
and bn ha a e in he sequence B.
(b) The e is a combina o ial in e p e a ion o Fo mula (3), ha is, an algo-
i hm ha we call he Minimum Excluded wi h Skipping algo i hm, ha akes
as inpu a sequence Dand ou pu s ou sequences A, B and Cand R. I
an, bn, cnand na e he n h e m o A, B, C and R, espec i ely, hen Equa-
ion (3) holds. Fu he mo e, he MES algo i hm cha ac e izes complemen a y
sequences. Speci ically, Aand Ba e complemen a y sequences i and only i
he e is a non-nega i e sequence C ha gene a es Aand B h ough he MES
algo i hm.
P oo . Fo mula (3) o Theo em 2 is e iden om he ac ha Aand Ba e comple-
men a y. Thus, he in ege s in he in e al (an, bn) will belong o ei he Ao B, and
hence he s a ed o mula in pa (a) mus ollow. The emainde o pa (a) holds
by cons uc ion as ollows. On he one hand, gi en a non-nega i e sequence C, he
MES can be implemen ed by skipping cnexcluded in ege s in he n h s ep. By con-
s uc ion, his will p oduce complemen a y sequences. Con e sely, i Cis nega i e,
skipping canno be pe o med in he na u al sense as i is done in he algo i hm.
On he o he hand, i a pai o complemen a y sequences is gi en, one can de ine n
as in De ini ion 7. Then cncan be de ined as he numbe o in ege s in he ollowing
complemen : [(an, bn)∩Bn]c(in o he wo ds, cn= #[(an, bn)∩Bn]c). Wi h his
se up, we can implemen he algo i hm wi h C={cn}∞
n=1. Then i ollows ha i
R={ n}∞
n=1, hen bn−an=cn+ n+ 1.
We now de elop a se ies o echnical lemmas ega ding S u mian and Bea y
sequences, and hen use hem o p o e Theo ems 3, 4 and 7.
INTEGERS: 25 (2025) 8
Gi en a Bea y sequence wi h slope 0 < α < 1, each posi i e in ege will occu
in he sequence k imes o k+ 1 imes, o some numbe k≥1. This is simply a
consequence o he size o α. We ha e he ollowing lemma.
Lemma 1. I αbelongs o he in e al 1
k+1 < α < 1
k o ka posi i e in ege ,
hen all non-nega i e in ege s appea in he Bea y sequence Cwi h slope α, each o
hem epea ing ko k+ 1 imes. Bo h occu ences a e in ini e. In he language o
so join, he e exis s, in his case, a sequence Bo non-nega i e in ege s such ha
C=B ⋆ Nk−1
0.
P oo . I is no ha d o see ha he inequali y 1
k+1 < α < 1
kimplies each non-
nega i e in ege epea s ko k+ 1 imes in {[αn]}∞
n=1. In ac , kα < 1 implies
ha each in ege koccu s a leas k imes, and an in ege canno occu k+ 2
imes o mo e. Fo i [nα] = [(n+ 1)α] = ··· = [(n+k+ 1)α]=k, hen 0 =
[(n+k+1)α]−[nα]≥[nα] + [(k+ 1)α]−[nα] = [(k+ 1)α]>1. Now, some in ege s
nwill need o be epea ed k+1 imes. This is so because i all la ge in ege s epea
k imes, hen he sequence would be ul ima ely pe iodic, and he ollowing equali y
would need o hold:
lim
n→∞
[nα]
n=1
k,
ha is, α=1
k, which con adic s he i a ionali y o α. Fo he same easons,
all la ge in ege s canno be epea ed k+ 1 imes. Hence, bo h kand k+ 1 occu
in ini ely o en.
The ollowing de ini ion will be used in he emaining o he pape .
De ini ion 8. Fo a eal numbe αsuch ha 0 <α<1, we de ine he cha ac e is ic
unc ion o αas
α(n)=[α(n+ 1)] −[αn].
Clea ly, α(n) = 1 o α(n) = 0. Since he sum elescopes, we ha e
m
X
n=1
α(n)=[α(m+ 1)]. (4)
Rema k 3. No ice ha Equa ion (4) gi es he numbe o in ege s n≤m o which
α(n) = 1.
Ano he de ini ion we will need is he ollowing one.
De ini ion 9. Fo 1 < β ∈R Q, de ine
g′
β(n) = (1i n= [kβ], o k∈Z,
0 o he wise.
INTEGERS: 25 (2025) 9
I is a well-known ac (see [26] and [4, Lemma 9.1.3]) ha o all in ege s n,
g′
β(n)= 1/β(n).
Lemma 2. Fo each i a ional numbe αsuch ha 1
k+1 < α < 1
k, he e exis s a
numbe β:= α
1−α, such ha [nα] = o k+ 1 di e en numbe s n=m, m +
1, . . . , m +k, i and only i [nβ]= o knumbe s n=q, q + 1, . . . , q +k−1.
In o he wo ds, i C= [nα]∞
n=1 and B=α
1−α·n∞
n=1
, hen C=D ⋆ Nk
0and
B=D ⋆ Nk−1
0 o some inc easing sequence Do non-nega i e in ege s.
P oo . No ice ha 1
k+1 < α < 1
ki and only i k < 1
α< k + 1, which is equi alen
o k−1<1
α−1< k and 1
α−1 = 1−α
α=1
β. Thus, we claim ha i is enough o
p o e ha he sequence [nα] equals o k+ 1 alues o n, i and only i
[( + 1) 1
α]−[ 1
α] = k+ 1.
Indeed, i his is ue, hen
[( + 1) 1
β]−[ 1
β] = [( + 1)( 1
α−1)] −[ (1
α−1)] = [( + 1) 1
α]−[ 1
α]−1=k,
i would hen ollow om his claim ha [nβ] epea s k imes. So we jus need o
p o e he double implica ion in he claim. Fo ha pu pose, om (8), we w i e
(n):= α(n) = [(n+ 1)α]−[nα]. And om (3), i ollows ha (n) = 1 i and
only i he e exis s a such ha n= [ 1
α]. Thus, om his las sen ence we ind ha
[α(n+m)] = o he i s k+1 alues o mi and only i he ollowing h ee hings
happen: i s , (n−1) = 0; second, (n)= (n+k+1) = 1; and hi d, (n+m) = 0
o all numbe s be ween nand n+k+ 1, i.e., o all msuch ha 1 ≤m<k+ 1.
Fo such an n, i ollows om (3) ha (n+m) = 0 o 1 ≤m<k+ 1 i and
only i he e is no jsuch ha n+m= [j1
α] o 1 ≤m≤k. Thus, we see ha
[( + 1) 1
α]−[ 1
α]> k. Since he di e ence be ween wo consecu i e numbe s in he
Bea y sequence [ 1
α] is ei he ko k+ 1, we see ha [( + 1) 1
α]−[ 1
α]=k+ 1.
The e o e, we ha e p o ed ha each ime he sequence [nα] epea s k+ 1 imes,
he di e ence [( + 1) 1
α]−[ 1
α] equals k+ 1, and hus, he lemma holds.
Combining Lemma 1 and Lemma 2, we see ha i a Bea y sequence is gene a ed
by an αsuch ha each non-nega i e in ege epea s ko k+ 1 imes, hen in he
Bea y sequence gene a ed by α
1−α=−1 + 1
1−α, in ege s epea k−1 o k imes. I
we i e a e his p ocess, we ob ain he ollowing lemma.
INTEGERS: 25 (2025) 16
Theo em 7. The MES algo i hm gene alizes he MEX algo i hm as ollows: Sup-
pose ha he e is an inc easing sequence o posi i e in ege s Dsuch ha C=
D ⋆ Nk−1
0 o some k∈N. Then we ha e he ollowing s a emen s.
1. I k= 2 and Dis he Bea y sequence de ined by he golden a io, hen he
MES and he MEX algo i hms coincide, i.e., hey bo h p oduce A(gi en by
he golden a io). In o he wo ds, he MES p oduces he sequence Ai and
only i he skipping sequence Ccan be de ined as ollows: any non-nega i e
in ege cappea s once o wice in C, and cappea s wice in Ci and only i
c∈A.
2. Le Dbe he sequence gi en by
α=k−1 + √k2+ 1
k.
Then he MES algo i hm p oduces he Bea y sequence Dand i s complemen .
In o he wo ds, he MES p oduces he sequence Di and only i he skipping
sequence Ccan be de ined as ollows: any non-nega i e in ege cappea s k
o k−1 imes in C, and cappea s k imes in Ci and only i c∈D. This
coincides wi h he MEX and he golden a io when k= 2.
P oo . Subs i u e α=δin o Equa ion (13), and sol e o δin he esul ing a ional
exp ession o ob ain a quad a ic i a ional wi h pa ame e k. The case k= 2 gi es
he i s pa o he co olla y.
Rema k 6. As seen in Equa ions (12) and (13), a gi en δcan gene a e in ini ely
many αs. Howe e , each gi en αis gene a ed by a unique choice o δand k.
Example 2. As an illus a ion o Theo em 6, conside he numbe α=187+2√13
113 .
The Bea y sequence gene a ed by αis {1,3,5,6,8,10,12,13,15,17,18, . . .}. I we
un he MES algo i hm wi h equency k= 3 and de ining sequence gi en by δ=
√13
2, we ob ain Table 6.
Example 3. Example 1 can be eph ased ecu si ely as ollows. The skipping
sequence Co he MES algo i hm ha gene a es he sequence Ade ined by he
golden a io is gi en by he condi ion “i n∈A, hen i will epea wice in C.
O he wise, nwill appea only once in C”. No e ha i δ=1+√5
2and k= 2, we
ob ain he sequence in Example 1, ha is, he sequence wi h he golden a io. In
his case he skipping sequence Cand he ou pu sequence Acoincide wi h he
de ining sequence D.
Table 6, below, shows he applica ion o he MES algo i hm when he equency
kis gi en by k= 3 and he de ining sequence Dis gi en by δ=√13/2. No e ha
he ou pu sequences Ais gi en by α=2−δ+ 2lδ
1+kδ =2−δ+ 6δ
1+6δ=187 + 2√13
113 .
INTEGERS: 25 (2025) 17
n h A B C R D
1) 1 2 0 0 1
2) 3 4 0 0 3
3) 5 7 1 0 5
4) 6 9 1 1 7
5) 8 11 1 1 9
6) 10 14 2 1 10
7) 12 16 2 1 12
8) 13 19 3 2 14
9) 15 21 3 2 16
10) 17 23 3 2 18
11) 18 26 4 3 19
12) 20 28 4 3 21
Table 6: I e a ions o he MES o k= 2 and δ=√13/2.
4. Concluding Rema ks
Wha does he MES algo i hm o e ha he MEX algo i hm does no ? No ice ha
bo h algo i hms allow us o gene a e any pai o Bea y sequences (and indeed any
pai o complemen a y sequences). The MEX algo i hm uses he unc ion bn−an=
hn o gene a e hese sequences, and any in e es ing applica ion equi es ha we be
able o easily desc ibe he unc ion hnindependen ly o anand bn.
To ob ain he Bea y sequences gene a ed by αand β, a ew cases a e s aigh -
o wa d o desc ibe. Fo example, [31] shows ha hn=ngi es he case α=1+√5
2.
Mo e gene ally, [15] and [19] show ha hn= n gi es he amily 2− +√ 2+1
2.
The MES algo i hm is mo e ad an ageous because i p o ides a gene al o mula
o hnas cn+ n+ 1, wi h explici o mulas o cnand nin he case o Bea y
sequences gi en in Theo em 2. I also o e s he added bene i o a combina o ial
in e p e a ion o cnand n, linking hem back o he complemen a y sequences A
and B. We conclude wi h an open ques ion. Gi en he many applica ions o he
MEX unc ion o he MEX algo i hm as highligh ed in Sec ion 1, does he MES
algo i hm e eal in e es ing connec ions ha illumina e some aspec s o hese ap-
plica ions o o complemen a y sequences in gene al?
Acknowledgemen s. The au ho is indeb ed o his ad iso , Kenne h B. S o -
la sky, o his guidance and he nume ous help ul discussions ha made his a icle
possible. He is also deeply g a e ul o he anonymous e e ee o a ca e ul ead-
ing o he manusc ip and signi ican sugges ions ha imp o ed he p esen a ion o
he ideas in he pape . Also, he au ho hanks he edi o o much app ecia ed
sugges ions imp o ing he pape . Finally, he hanks Michel Dekking o some help-
INTEGERS: 25 (2025) 18
ul commen s inco po a ed in o he ini ial sec ion o he pape and o his aluable
p oo eading eedback. This esea ch has been pa ially suppo ed by he Minis e io
de Educaci´on Supe io , Ciencia y Tecnolog´ıa (MESCyT) o he Dominican Republic,
g an s No. FONDOCyT: 2018-2019-1D2-261 and FODOCyT: 2018-2019-1D2-262.
Re e ences
[1] A. G. Abe c ombie, Bea y sequences and mul iplica i e numbe heo y, Ac a A i h.70 (1995),
195-207.
[2] A. G. Abe c ombie, W. Banks and I. Shpa linski, A i hme ic unc ions on Bea y sequences,
Ac a A i h.136 (2009), 81-89.
[3] J. Allouche and F. Dekking, Gene alized Bea y sequences and complemen a y iples, Mosc.
J. Comb. Numbe Theo y .8(2019), 325-341.
[4] J. Allouche and J. Shalli , Au oma ic Sequences: Theo y, Applica ions and Gene aliza ions,
Camb idge uni e si y p ess, New Yo k, 2003.
[5] G. And ews and D. Newman, Pa i ions and he minimal excludan , Ann. Comb..23 (2019),
249-254.
[6] C. Ballo , On Func ions Exp essible as Wo ds on a Pai o Bea y Sequences, J. In ege Seq..
20 (2017), a icle 17.4.2.
[7] W. Banks and I. Shpa linski, P ime numbe s wi h Bea y sequences, Colloq. Ma h. 115 (2007),
147-157.
[8] S. Bea y, P oblem 3173, Ame . Ma h. Mon hly 33 (1926), 159. Solu ions, ibid., 34 (1927),
159.
[9] J. Be s el, Random gene a ion o ini e S u mian wo ds, Disc e e Ma h. 153 (1996), 29–39.
[10] F. Blanche -Sad i and S. Simmons, Coun ing minimal semi-S u mian wo ds, Disc e e Appl.
Ma h.161 (2013), 2851-2861.
[11] W. Bosma, M. Dekking and W. S eine , A Rema kable In ege Sequence Rela ed o πand
√2, In ege s.18, (2018), 1-9.
[12] N. B e ell, J. Oxley, C. Semple and G. Whi le, The excluded mino s o 2-and 3- egula
ma oids, p ep in A Xi :2206.15188.
[13] A. B ucks ein, Sel -simila i y p ope ies o digi ized s aigh lines, Con emp. Ma h.119
(1991), 1-20 .
[14] J. Conway, On Numbe s and Games, London Ma hema ical Socie y Monog aphs, London,
1976.
[15] A. F aenkel, How o Bea You Wy ho Games’ Opponen on Th ee F on s, Ame . Ma h.
Mon hly.89 (1982), 353-361.
[16] A. F aenkel, I e a ed loo unc ion, algeb aic numbe s, disc e e chaos, Bea y subsequences,
semig oups, T ans. Ame . Ma h. Soc..341 (1994), 639-664.
[17] M. Ha a, Neu ons: A Ma hema ical Igni ion, Wo ld Scien i ic, 2014.
INTEGERS: 25 (2025) 19
[18] A. Hildeb and, J. Li, X. Li, and Y. Xie, Almos Bea y Pa i ions, p ep in A Xi :1809.08690.
[19] J. Holladay, Some gene aliza ions o Wy ho ’s game and o he ela ed games, Ma h. Mag..
41 (1968), 7-13.
[20] F. Illingwo h, A. Sco and D. Wood, P oduc s uc u e o g aphs wi h an excluded mino ,
p ep in A Xi :2104.06627.
[21] M. Mo se and G. Hedlund, Symbolic dynamics II. S u mian ajec o ies, Ame . J. Ma h..62
(1940), 1-42.
[22] M. Lo hai e, Algeb aic Combina o ics on Wo ds, Camb idge uni e si y p ess, New Yo k,
2002.
[23] F. Luca, G. Polanco and W. Zudilin, A a ia ion on he heme o Nicomachus, Bull. Aus .
Ma h. Soc..97 (2018), 367-373.
[24] T. Noll, S u mian sequences and mo phisms: a music- heo e ical applica ion, Ma h´ema ique
E Musique, Jou n´ee Annuelle De La Soci´e ´e Ma h´ema ique De F ance (2008), 79-102.
[25] K. O’B yan , A gene a ing unc ion echnique o Bea y sequences and o he s ep sequences,
J. Numbe Theo y.94 (2002), 299-319.
[26] G. Polanco, The loga i hm o i a ional numbe s and Bea y sequences, Ac a A i h..179
(2017), 101-123.
[27] H. Po a and K. S ola sky, Hal -sil e ed mi o s and Wy ho ’s game, Canad. Ma h. Bull..
33 (1990), 119-125.
[28] K. S ola sky, Bea y sequences, con inued ac ions, and ce ain shi ope a o s, Canad. Ma h.
Bull..19 (1976), 473-482.
[29] H. Tang, P ime di iso s in special Bea y sequences, Chinese J. Con emp. Ma h. (2010),
221-230.
[30] D. Welsh and M. Powell, An uppe bound o he ch oma ic numbe o a g aph and i s
applica ion o ime abling p oblems, The Compu e Jou nal.10 (1967), 85-86.
[31] W. Wy ho , A modi ica ion o he game o Nim, Nieuw A ch. Wisk.7(1907), 199-202.
