Modified Padovan words and the maximum number of runs in a word
Jamie Simpson · eSpace (Curtin University) · 2010
A run (or maximal periodicity) in a word is a periodic factor whose length is at least twice the period and which cannot be extended to the left or right without changing the period.Recently Kusano et al. [6] used a clever search technique to find run-rich words and were able to show that the number of runs in a word of length n can be greater than 0.94457564n.In this paper we use a two-stage process to construct words with a (very slightly) higher run density than theirs.We first produce ternary words which we call Modified Padovan words, then apply a morphism to these to produce run-rich binary words.The Modified Padovan words have interesting and surprising properties.