# Common words#

AUTHORS:

• Franco Saliola (2008-12-17): merged into sage

• Sébastien Labbé (2008-12-17): merged into sage

• Arnaud Bergeron (2008-12-17): merged into sage

• Amy Glen (2008-12-17): merged into sage

USE:

To see a list of all word constructors, type words. and then press the Tab key. The documentation for each constructor includes information about each word, which provides a useful reference.

REFERENCES:

[AC03]

B. Adamczewski, J. Cassaigne, On the transcendence of real numbers with a regular expansion, J. Number Theory 103 (2003) 27–37.

[BmBGL07]

A. Blondin-Massé, S. Brlek, A. Glen, and S. Labbé. On the critical exponent of generalized Thue-Morse words. Discrete Math. Theor. Comput. Sci. 9 (1):293–304, 2007.

[BmBGL09] (1,2)

A. Blondin-Massé, S. Brlek, A. Garon, and S. Labbé. Christoffel and Fibonacci Tiles, DGCI 2009, Montreal, to appear in LNCS.

[Loth02] (1,2,3)

M. Lothaire, Algebraic Combinatorics On Words, vol. 90 of Encyclopedia of Mathematics and its Applications, Cambridge University Press, U.K., 2002.

EXAMPLES:

sage: t = words.ThueMorseWord(); t
word: 0110100110010110100101100110100110010110...

>>> from sage.all import *
>>> t = words.ThueMorseWord(); t
word: 0110100110010110100101100110100110010110...

class sage.combinat.words.word_generators.LowerChristoffelWord(p, q, alphabet=(0, 1), algorithm='cf')[source]#

Returns the lower Christoffel word of slope $$p/q$$, where $$p$$ and $$q$$ are relatively prime non-negative integers, over the given two-letter alphabet.

The Christoffel word of slope p/q is obtained from the Cayley graph of $$\ZZ/(p+q)\ZZ$$ with generator $$q$$ as follows. If $$u \rightarrow v$$ is an edge in the Cayley graph, then $$v = u + p \mod{p+q}$$. Label the edge $$u \rightarrow v$$ by alphabet[1] if $$u < v$$ and alphabet[0] otherwise. The Christoffel word is the word obtained by reading the edge labels along the cycle beginning from 0.

EXAMPLES:

sage: words.LowerChristoffelWord(4,7)
word: 00100100101

>>> from sage.all import *
>>> words.LowerChristoffelWord(Integer(4),Integer(7))
word: 00100100101

sage: words.LowerChristoffelWord(4,7,alphabet='ab')
word: aabaabaabab

>>> from sage.all import *
>>> words.LowerChristoffelWord(Integer(4),Integer(7),alphabet='ab')
word: aabaabaabab

markoff_number()[source]#

Return the Markoff number associated to the Christoffel word self.

The Markoff number of a Christoffel word $$w$$ is $$trace(M(w))/3$$, where $$M(w)$$ is the $$2\times 2$$ matrix obtained by applying the morphism: 0 -> matrix(2,[2,1,1,1]) 1 -> matrix(2,[5,2,2,1])

EXAMPLES:

sage: w0 = words.LowerChristoffelWord(4,7)
sage: w1, w2 = w0.standard_factorization()
sage: (m0,m1,m2) = (w.markoff_number() for w in (w0,w1,w2))                 # needs sage.modules
sage: (m0,m1,m2)                                                            # needs sage.modules
(294685, 13, 7561)
sage: m0**2 + m1**2 + m2**2 == 3*m0*m1*m2                                   # needs sage.modules
True

>>> from sage.all import *
>>> w0 = words.LowerChristoffelWord(Integer(4),Integer(7))
>>> w1, w2 = w0.standard_factorization()
>>> (m0,m1,m2) = (w.markoff_number() for w in (w0,w1,w2))                 # needs sage.modules
>>> (m0,m1,m2)                                                            # needs sage.modules
(294685, 13, 7561)
>>> m0**Integer(2) + m1**Integer(2) + m2**Integer(2) == Integer(3)*m0*m1*m2                                   # needs sage.modules
True

standard_factorization()[source]#

Returns the standard factorization of the Christoffel word self.

The standard factorization of a Christoffel word $$w$$ is the unique factorization of $$w$$ into two Christoffel words.

EXAMPLES:

sage: w = words.LowerChristoffelWord(5,9)
sage: w
word: 00100100100101
sage: w1, w2 = w.standard_factorization()
sage: w1
word: 001
sage: w2
word: 00100100101

>>> from sage.all import *
>>> w = words.LowerChristoffelWord(Integer(5),Integer(9))
>>> w
word: 00100100100101
>>> w1, w2 = w.standard_factorization()
>>> w1
word: 001
>>> w2
word: 00100100101

sage: w = words.LowerChristoffelWord(51,37)
sage: w1, w2 = w.standard_factorization()
sage: w1
word: 0101011010101101011
sage: w2
word: 0101011010101101011010101101010110101101...
sage: w1 * w2 == w
True

>>> from sage.all import *
>>> w = words.LowerChristoffelWord(Integer(51),Integer(37))
>>> w1, w2 = w.standard_factorization()
>>> w1
word: 0101011010101101011
>>> w2
word: 0101011010101101011010101101010110101101...
>>> w1 * w2 == w
True

class sage.combinat.words.word_generators.WordGenerator[source]#

Bases: object

Constructor of several famous words.

EXAMPLES:

sage: words.ThueMorseWord()
word: 0110100110010110100101100110100110010110...

>>> from sage.all import *
>>> words.ThueMorseWord()
word: 0110100110010110100101100110100110010110...

sage: words.FibonacciWord()
word: 0100101001001010010100100101001001010010...

>>> from sage.all import *
>>> words.FibonacciWord()
word: 0100101001001010010100100101001001010010...

sage: words.ChristoffelWord(5, 8)
word: 0010010100101

>>> from sage.all import *
>>> words.ChristoffelWord(Integer(5), Integer(8))
word: 0010010100101

sage: words.RandomWord(10, 4)    # not tested random
word: 1311131221

>>> from sage.all import *
>>> words.RandomWord(Integer(10), Integer(4))    # not tested random
word: 1311131221

sage: words.CodingOfRotationWord(alpha=0.618, beta=0.618)
word: 1010110101101101011010110110101101101011...

>>> from sage.all import *
>>> words.CodingOfRotationWord(alpha=RealNumber('0.618'), beta=RealNumber('0.618'))
word: 1010110101101101011010110110101101101011...

sage: tm = WordMorphism('a->ab,b->ba')
sage: fib = WordMorphism('a->ab,b->a')
sage: tmword = words.ThueMorseWord([0, 1])
sage: from itertools import repeat
word: abbaababbaabbaabbaababbaababbaabbaababba...

>>> from sage.all import *
>>> tm = WordMorphism('a->ab,b->ba')
>>> fib = WordMorphism('a->ab,b->a')
>>> tmword = words.ThueMorseWord([Integer(0), Integer(1)])
>>> from itertools import repeat
word: abbaababbaabbaabbaababbaababbaabbaababba...


Note

To see a list of all word constructors, type words. and then hit the Tab key. The documentation for each constructor includes information about each word, which provides a useful reference.

BaumSweetWord()[source]#

Returns the Baum-Sweet Word.

The Baum-Sweet Sequence is an infinite word over the alphabet $$\{0,1\}$$ defined by the following string substitution rules:

$$00 \rightarrow 0000$$

$$01 \rightarrow 1001$$

$$10 \rightarrow 0100$$

$$11 \rightarrow 1101$$

The substitution rule above can be considered as a morphism on the submonoid of $$\{0,1\}$$ generated by $$\{00,01,10,11\}$$ (which is a free monoid on these generators).

It is also defined as the concatenation of the terms from the Baum-Sweet Sequence:

$\begin{split}b_n = \begin{cases} 0, & \text{if } n = 0 \\ 1, & \text{if } m \text{ is even} \\ b_{\frac{m-1}{2}}, & \text{if } m \text{ is odd} \end{cases}\end{split}$

where $$n=m4^k$$ and $$m$$ is not divisible by 4 if $$m \neq 0$$.

The individual terms of the Baum-Sweet Sequence are also given by:

$\begin{split}b_n = \begin{cases} 1, & \text{if the binary representation of} n \text{ contains no block of consecutive 0's of odd length}\\ 0, & \text{otherwise}\\ \end{cases}\\\end{split}$

for $$n > 0$$ with $$b_0 = 1$$.

EXAMPLES:

Baum-Sweet Word:

sage: w = words.BaumSweetWord(); w
word: 1101100101001001100100000100100101001001...

>>> from sage.all import *
>>> w = words.BaumSweetWord(); w
word: 1101100101001001100100000100100101001001...


Block Definition:

sage: w = words.BaumSweetWord()
sage: f = lambda n: '1' if all(len(x)%2==0 for x in bin(n)[2:].split('1')) else '0'
sage: all(f(i) == w[i] for i in range(1,100))
True

>>> from sage.all import *
>>> w = words.BaumSweetWord()
>>> f = lambda n: '1' if all(len(x)%Integer(2)==Integer(0) for x in bin(n)[Integer(2):].split('1')) else '0'
>>> all(f(i) == w[i] for i in range(Integer(1),Integer(100)))
True

CharacteristicSturmianWord(slope, alphabet=(0, 1), bits=None)[source]#

Returns the characteristic Sturmian word (also called standard Sturmian word) of given slope.

Over a binary alphabet $$\{a,b\}$$, the characteristic Sturmian word $$c_\alpha$$ of irrational slope $$\alpha$$ is the infinite word satisfying $$s_{\alpha,0} = ac_\alpha$$ and $$s'_{\alpha,0} = bc_\alpha$$, where $$s_{\alpha,0}$$ and $$s'_{\alpha,0}$$ are respectively the lower and upper mechanical words with slope $$\alpha$$ and intercept $$0$$. Equivalently, for irrational $$\alpha$$, $$c_\alpha = s_{\alpha,\alpha} = s'_{\alpha,\alpha}$$.

Let $$\alpha = [0, d_1 + 1, d_2, d_3, \ldots]$$ be the continued fraction expansion of $$\alpha$$. It has been shown that the characteristic Sturmian word of slope $$\alpha$$ is also the limit of the sequence: $$s_0 = b, s_1 = a, \ldots, s_{n+1} = s_n^{d_n} s_{n-1}$$ for $$n > 0$$.

See Section 2.1 of [Loth02] for more details.

INPUT:

• slope – the slope of the word. It can be one of the following:

• real number in $$]0, 1[$$

• iterable over the continued fraction expansion of a real number in $$]0, 1[$$

• alphabet – any container of length two that is suitable to build an instance of OrderedAlphabet (list, tuple, str, …)

• bits – integer (optional and considered only if slope is a real number) the number of bits to consider when computing the continued fraction.

OUTPUT:

word

ALGORITHM:

Let $$[0, d_1 + 1, d_2, d_3, \ldots]$$ be the continued fraction expansion of $$\alpha$$. Then, the characteristic Sturmian word of slope $$\alpha$$ is the limit of the sequence: $$s_0 = b$$, $$s_1 = a$$ and $$s_{n+1} = s_n^{d_n} s_{n-1}$$ for $$n > 0$$.

EXAMPLES:

From real slope:

sage: words.CharacteristicSturmianWord(1/golden_ratio^2)                    # needs sage.symbolic
word: 0100101001001010010100100101001001010010...
sage: words.CharacteristicSturmianWord(4/5)                                 # needs sage.rings.real_mpfr
word: 11110
sage: words.CharacteristicSturmianWord(5/14)                                # needs sage.rings.real_mpfr
word: 01001001001001
sage: words.CharacteristicSturmianWord(pi - 3)                              # needs sage.symbolic
word: 0000001000000100000010000001000000100000...

>>> from sage.all import *
>>> words.CharacteristicSturmianWord(Integer(1)/golden_ratio**Integer(2))                    # needs sage.symbolic
word: 0100101001001010010100100101001001010010...
>>> words.CharacteristicSturmianWord(Integer(4)/Integer(5))                                 # needs sage.rings.real_mpfr
word: 11110
>>> words.CharacteristicSturmianWord(Integer(5)/Integer(14))                                # needs sage.rings.real_mpfr
word: 01001001001001
>>> words.CharacteristicSturmianWord(pi - Integer(3))                              # needs sage.symbolic
word: 0000001000000100000010000001000000100000...


From an iterator of the continued fraction expansion of a real:

sage: def cf():
....:   yield 0
....:   yield 2
....:   while True: yield 1
sage: F = words.CharacteristicSturmianWord(cf()); F                         # needs sage.rings.real_mpfr
word: 0100101001001010010100100101001001010010...
sage: Fib = words.FibonacciWord(); Fib
word: 0100101001001010010100100101001001010010...
sage: F[:10000] == Fib[:10000]                                              # needs sage.rings.real_mpfr
True

>>> from sage.all import *
>>> def cf():
...   yield Integer(0)
...   yield Integer(2)
...   while True: yield Integer(1)
>>> F = words.CharacteristicSturmianWord(cf()); F                         # needs sage.rings.real_mpfr
word: 0100101001001010010100100101001001010010...
>>> Fib = words.FibonacciWord(); Fib
word: 0100101001001010010100100101001001010010...
>>> F[:Integer(10000)] == Fib[:Integer(10000)]                                              # needs sage.rings.real_mpfr
True


The alphabet may be specified:

sage: words.CharacteristicSturmianWord(cf(), 'rs')                          # needs sage.rings.real_mpfr
word: rsrrsrsrrsrrsrsrrsrsrrsrrsrsrrsrrsrsrrsr...

>>> from sage.all import *
>>> words.CharacteristicSturmianWord(cf(), 'rs')                          # needs sage.rings.real_mpfr
word: rsrrsrsrrsrrsrsrrsrsrrsrrsrsrrsrrsrsrrsr...


The characteristic sturmian word of slope $$(\sqrt{3}-1)/2$$:

sage: words.CharacteristicSturmianWord((sqrt(3)-1)/2)                       # needs sage.symbolic
word: 0100100101001001001010010010010100100101...

>>> from sage.all import *
>>> words.CharacteristicSturmianWord((sqrt(Integer(3))-Integer(1))/Integer(2))                       # needs sage.symbolic
word: 0100100101001001001010010010010100100101...


The same word defined from the continued fraction expansion of $$(\sqrt{3}-1)/2$$:

sage: from itertools import cycle, chain
sage: it = chain([0], cycle([2, 1]))
sage: words.CharacteristicSturmianWord(it)
word: 0100100101001001001010010010010100100101...

>>> from sage.all import *
>>> from itertools import cycle, chain
>>> it = chain([Integer(0)], cycle([Integer(2), Integer(1)]))
>>> words.CharacteristicSturmianWord(it)
word: 0100100101001001001010010010010100100101...


The first terms of the standard sequence of the characteristic sturmian word of slope $$(\sqrt{3}-1)/2$$:

sage: words.CharacteristicSturmianWord([0,2])
word: 01
sage: words.CharacteristicSturmianWord([0,2,1])
word: 010
sage: words.CharacteristicSturmianWord([0,2,1,2])
word: 01001001
sage: words.CharacteristicSturmianWord([0,2,1,2,1])
word: 01001001010
sage: words.CharacteristicSturmianWord([0,2,1,2,1,2])
word: 010010010100100100101001001001
sage: words.CharacteristicSturmianWord([0,2,1,2,1,2,1])
word: 0100100101001001001010010010010100100101...

>>> from sage.all import *
>>> words.CharacteristicSturmianWord([Integer(0),Integer(2)])
word: 01
>>> words.CharacteristicSturmianWord([Integer(0),Integer(2),Integer(1)])
word: 010
>>> words.CharacteristicSturmianWord([Integer(0),Integer(2),Integer(1),Integer(2)])
word: 01001001
>>> words.CharacteristicSturmianWord([Integer(0),Integer(2),Integer(1),Integer(2),Integer(1)])
word: 01001001010
>>> words.CharacteristicSturmianWord([Integer(0),Integer(2),Integer(1),Integer(2),Integer(1),Integer(2)])
word: 010010010100100100101001001001
>>> words.CharacteristicSturmianWord([Integer(0),Integer(2),Integer(1),Integer(2),Integer(1),Integer(2),Integer(1)])
word: 0100100101001001001010010010010100100101...

ChristoffelWord[source]#

alias of LowerChristoffelWord

CodingOfRotationWord(alpha, beta, x=0, alphabet=(0, 1))[source]#

Returns the infinite word obtained from the coding of rotation of parameters $$(\alpha,\beta, x)$$ over the given two-letter alphabet.

The coding of rotation corresponding to the parameters $$(\alpha,\beta, x)$$ is the symbolic sequence $$u = (u_n)_{n\geq 0}$$ defined over the binary alphabet $$\{0, 1\}$$ by $$u_n = 1$$ if $$x+n\alpha\in[0, \beta[$$ and $$u_n = 0$$ otherwise. See [AC03].

EXAMPLES:

sage: alpha = 0.45
sage: beta = 0.48
sage: words.CodingOfRotationWord(0.45, 0.48)
word: 1101010101001010101011010101010010101010...

>>> from sage.all import *
>>> alpha = RealNumber('0.45')
>>> beta = RealNumber('0.48')
>>> words.CodingOfRotationWord(RealNumber('0.45'), RealNumber('0.48'))
word: 1101010101001010101011010101010010101010...

sage: words.CodingOfRotationWord(0.45, 0.48, alphabet='xy')
word: yyxyxyxyxyxxyxyxyxyxyyxyxyxyxyxxyxyxyxyx...

>>> from sage.all import *
>>> words.CodingOfRotationWord(RealNumber('0.45'), RealNumber('0.48'), alphabet='xy')
word: yyxyxyxyxyxxyxyxyxyxyyxyxyxyxyxxyxyxyxyx...

FibonacciWord(alphabet=(0, 1), construction_method='recursive')[source]#

Returns the Fibonacci word on the given two-letter alphabet.

INPUT:

• alphabet – any container of length two that is suitable to build an instance of OrderedAlphabet (list, tuple, str, …)

• construction_method – can be any of the following: “recursive”, “fixed point”, “function” (see below for definitions).

Recursive construction: the Fibonacci word is the limit of the following sequence of words: $$S_0 = 0$$, $$S_1 = 01$$, $$S_n = S_{n-1} S_{n-2}$$ for $$n \geq 2$$.

Fixed point construction: the Fibonacci word is the fixed point of the morphism: $$0 \mapsto 01$$ and $$1 \mapsto 0$$. Hence, it can be constructed by the following read-write process:

1. beginning at the first letter of $$01$$,

2. if the next letter is $$0$$, append $$01$$ to the word;

3. if the next letter is $$1$$, append $$1$$ to the word;

4. move to the next letter of the word.

Function: Over the alphabet $$\{1, 2\}$$, the n-th letter of the Fibonacci word is $$\lfloor (n+2) \varphi \rfloor - \lfloor (n+1) \varphi \rfloor$$ where $$\varphi=(1+\sqrt{5})/2$$ is the golden ratio.

EXAMPLES:

sage: w = words.FibonacciWord(construction_method="recursive"); w
word: 0100101001001010010100100101001001010010...

>>> from sage.all import *
>>> w = words.FibonacciWord(construction_method="recursive"); w
word: 0100101001001010010100100101001001010010...

sage: v = words.FibonacciWord(construction_method="recursive", alphabet='ab'); v
word: abaababaabaababaababaabaababaabaababaaba...

>>> from sage.all import *
>>> v = words.FibonacciWord(construction_method="recursive", alphabet='ab'); v
word: abaababaabaababaababaabaababaabaababaaba...

sage: u = words.FibonacciWord(construction_method="fixed point"); u
word: 0100101001001010010100100101001001010010...

>>> from sage.all import *
>>> u = words.FibonacciWord(construction_method="fixed point"); u
word: 0100101001001010010100100101001001010010...

sage: words.FibonacciWord(construction_method="fixed point", alphabet=[4, 1])
word: 4144141441441414414144144141441441414414...

>>> from sage.all import *
>>> words.FibonacciWord(construction_method="fixed point", alphabet=[Integer(4), Integer(1)])
word: 4144141441441414414144144141441441414414...

sage: words.FibonacciWord([0,1], 'function')                                # needs sage.symbolic
word: 0100101001001010010100100101001001010010...
sage: words.FibonacciWord('ab', 'function')                                 # needs sage.symbolic
word: abaababaabaababaababaabaababaabaababaaba...

>>> from sage.all import *
>>> words.FibonacciWord([Integer(0),Integer(1)], 'function')                                # needs sage.symbolic
word: 0100101001001010010100100101001001010010...
>>> words.FibonacciWord('ab', 'function')                                 # needs sage.symbolic
word: abaababaabaababaababaabaababaabaababaaba...

FixedPointOfMorphism(morphism, first_letter)[source]#

Returns the fixed point of the morphism beginning with first_letter.

A fixed point of a morphism $$\varphi$$ is a word $$w$$ such that $$\varphi(w) = w$$.

INPUT:

• morphism – endomorphism prolongable on first_letter. It must be something that WordMorphism’s constructor understands (dict, str, …).

• first_letter – the first letter of the fixed point

OUTPUT:

The fixed point of the morphism beginning with first_letter

EXAMPLES:

sage: mu = {0:[0,1], 1:[1,0]}
sage: tm = words.FixedPointOfMorphism(mu,0); tm
word: 0110100110010110100101100110100110010110...
sage: TM = words.ThueMorseWord()
sage: tm[:1000] == TM[:1000]                                                # needs sage.modules
True

>>> from sage.all import *
>>> mu = {Integer(0):[Integer(0),Integer(1)], Integer(1):[Integer(1),Integer(0)]}
>>> tm = words.FixedPointOfMorphism(mu,Integer(0)); tm
word: 0110100110010110100101100110100110010110...
>>> TM = words.ThueMorseWord()
>>> tm[:Integer(1000)] == TM[:Integer(1000)]                                                # needs sage.modules
True

sage: mu = {0:[0,1], 1:[0]}
sage: f = words.FixedPointOfMorphism(mu,0); f
word: 0100101001001010010100100101001001010010...
sage: F = words.FibonacciWord(); F
word: 0100101001001010010100100101001001010010...
sage: f[:1000] == F[:1000]                                                  # needs sage.modules
True

>>> from sage.all import *
>>> mu = {Integer(0):[Integer(0),Integer(1)], Integer(1):[Integer(0)]}
>>> f = words.FixedPointOfMorphism(mu,Integer(0)); f
word: 0100101001001010010100100101001001010010...
>>> F = words.FibonacciWord(); F
word: 0100101001001010010100100101001001010010...
>>> f[:Integer(1000)] == F[:Integer(1000)]                                                  # needs sage.modules
True

sage: fp = words.FixedPointOfMorphism('a->abc,b->,c->','a'); fp
word: abc

>>> from sage.all import *
>>> fp = words.FixedPointOfMorphism('a->abc,b->,c->','a'); fp
word: abc

KolakoskiWord(alphabet=(1, 2))[source]#

Returns the Kolakoski word over the given alphabet and starting with the first letter of the alphabet.

Let $$A = \{a,b\}$$ be an alphabet, where $$a$$ and $$b$$ are two distinct positive integers. The Kolakoski word $$K_{a,b}$$ over $$A$$ and starting with $$a$$ is the unique infinite word $$w$$ such that $$w = \Delta(w)$$, where $$\Delta(w)$$ is the word encoding the runs of $$w$$ (see delta() method on words for more details).

Note that $$K_{a,b} \neq K_{b,a}$$. On the other hand, the words $$K_{a,b}$$ and $$K_{b,a}$$ are the unique two words over $$A$$ that are fixed by $$\Delta$$.

Also note that the Kolakoski word is also known as the Oldenburger word.

INPUT:

• alphabet – (default: (1,2)) an iterable of two positive integers

OUTPUT:

infinite word

EXAMPLES:

The usual Kolakoski word:

sage: w = words.KolakoskiWord()
sage: w
word: 1221121221221121122121121221121121221221...
sage: w.delta()
word: 1221121221221121122121121221121121221221...

>>> from sage.all import *
>>> w = words.KolakoskiWord()
>>> w
word: 1221121221221121122121121221121121221221...
>>> w.delta()
word: 1221121221221121122121121221121121221221...


The other Kolakoski word on the same alphabet:

sage: w = words.KolakoskiWord(alphabet = (2,1))
sage: w
word: 2211212212211211221211212211211212212211...
sage: w.delta()
word: 2211212212211211221211212211211212212211...

>>> from sage.all import *
>>> w = words.KolakoskiWord(alphabet = (Integer(2),Integer(1)))
>>> w
word: 2211212212211211221211212211211212212211...
>>> w.delta()
word: 2211212212211211221211212211211212212211...


It is naturally generalized to any two integers alphabet:

sage: w = words.KolakoskiWord(alphabet = (2,5))
sage: w
word: 2255222225555522552255225555522222555552...
sage: w.delta()
word: 2255222225555522552255225555522222555552...

>>> from sage.all import *
>>> w = words.KolakoskiWord(alphabet = (Integer(2),Integer(5)))
>>> w
word: 2255222225555522552255225555522222555552...
>>> w.delta()
word: 2255222225555522552255225555522222555552...


REFERENCES:

[Kolakoski66]

William Kolakoski, proposal 5304, American Mathematical Monthly 72 (1965), 674; for a partial solution, see “Self Generating Runs,” by Necdet Üçoluk, Amer. Math. Mon. 73 (1966), 681-2.

LowerChristoffelWord[source]#

alias of LowerChristoffelWord

LowerMechanicalWord(alpha, rho=0, alphabet=None)[source]#

Returns the lower mechanical word with slope $$\alpha$$ and intercept $$\rho$$

The lower mechanical word $$s_{\alpha,\rho}$$ with slope $$\alpha$$ and intercept $$\rho$$ is defined by $$s_{\alpha,\rho}(n) = \lfloor\alpha(n+1) + \rho\rfloor - \lfloor\alpha n + \rho\rfloor$$. [Loth02]

INPUT:

• alpha – real number such that $$0 \leq\alpha\leq 1$$

• rho – real number (default: 0)

• alphabet – iterable of two elements or None (default: None)

OUTPUT:

infinite word

EXAMPLES:

sage: words.LowerMechanicalWord(1/golden_ratio^2)                           # needs sage.symbolic
word: 0010010100100101001010010010100100101001...
sage: words.LowerMechanicalWord(1/5)                                        # needs sage.symbolic
word: 0000100001000010000100001000010000100001...
sage: words.LowerMechanicalWord(1/pi)                                       # needs sage.symbolic
word: 0001001001001001001001000100100100100100...

>>> from sage.all import *
>>> words.LowerMechanicalWord(Integer(1)/golden_ratio**Integer(2))                           # needs sage.symbolic
word: 0010010100100101001010010010100100101001...
>>> words.LowerMechanicalWord(Integer(1)/Integer(5))                                        # needs sage.symbolic
word: 0000100001000010000100001000010000100001...
>>> words.LowerMechanicalWord(Integer(1)/pi)                                       # needs sage.symbolic
word: 0001001001001001001001000100100100100100...

MinimalSmoothPrefix(n)[source]#

This function finds and returns the minimal smooth prefix of length n.

See [BMP2007] for a definition.

INPUT:

• n – the desired length of the prefix

OUTPUT:

word – the prefix

Note

Be patient, this function can take a really long time if asked for a large prefix.

EXAMPLES:

sage: words.MinimalSmoothPrefix(10)
word: 1212212112

>>> from sage.all import *
>>> words.MinimalSmoothPrefix(Integer(10))
word: 1212212112

PalindromicDefectWord(k=1, alphabet='ab')[source]#

Return the finite word $$w = a b^k a b^{k-1} a a b^{k-1} a b^{k} a$$.

As described by Brlek, Hamel, Nivat and Reutenauer in [BHNR2004], this finite word $$w$$ is such that the infinite periodic word $$w^{\omega}$$ has palindromic defect k.

INPUT:

• k – positive integer (default: 1)

• alphabet – iterable (default: 'ab') of size two

OUTPUT:

finite word

EXAMPLES:

sage: words.PalindromicDefectWord(10)
word: abbbbbbbbbbabbbbbbbbbaabbbbbbbbbabbbbbbb...

>>> from sage.all import *
>>> words.PalindromicDefectWord(Integer(10))
word: abbbbbbbbbbabbbbbbbbbaabbbbbbbbbabbbbbbb...

sage: w = words.PalindromicDefectWord(3)
sage: w
word: abbbabbaabbabbba
sage: w.defect()
0
sage: (w^2).defect()
3
sage: (w^3).defect()
3

>>> from sage.all import *
>>> w = words.PalindromicDefectWord(Integer(3))
>>> w
word: abbbabbaabbabbba
>>> w.defect()
0
>>> (w**Integer(2)).defect()
3
>>> (w**Integer(3)).defect()
3


On other alphabets:

sage: words.PalindromicDefectWord(3, alphabet='cd')
word: cdddcddccddcdddc
sage: words.PalindromicDefectWord(3, alphabet=['c', 3])
word: c333c33cc33c333c

>>> from sage.all import *
>>> words.PalindromicDefectWord(Integer(3), alphabet='cd')
word: cdddcddccddcdddc
>>> words.PalindromicDefectWord(Integer(3), alphabet=['c', Integer(3)])
word: c333c33cc33c333c

RandomWord(n, m=2, alphabet=None)[source]#

Return a random word of length $$n$$ over the given $$m$$-letter alphabet.

INPUT:

• n – integer, the length of the word

• m – integer (default 2), the size of the output alphabet

• alphabet – (default is $$\{0,1,...,m-1\}$$) any container of length m that is suitable to build an instance of OrderedAlphabet (list, tuple, str, …)

EXAMPLES:

sage: words.RandomWord(10)         # random results
word: 0110100101
sage: words.RandomWord(10, 4)      # random results
word: 0322313320
sage: words.RandomWord(100, 7)     # random results
word: 2630644023642516442650025611300034413310...
sage: words.RandomWord(100, 7, range(-3,4))  # random results
word: 1,3,-1,-1,3,2,2,0,1,-2,1,-1,-3,-2,2,0,3,0,-3,0,3,0,-2,-2,2,0,1,-3,2,-2,-2,2,0,2,1,-2,-3,-2,-1,0,...
sage: words.RandomWord(100, 5, "abcde") # random results
sage: words.RandomWord(17, 5, "abcde")     # random results

>>> from sage.all import *
>>> words.RandomWord(Integer(10))         # random results
word: 0110100101
>>> words.RandomWord(Integer(10), Integer(4))      # random results
word: 0322313320
>>> words.RandomWord(Integer(100), Integer(7))     # random results
word: 2630644023642516442650025611300034413310...
>>> words.RandomWord(Integer(100), Integer(7), range(-Integer(3),Integer(4)))  # random results
word: 1,3,-1,-1,3,2,2,0,1,-2,1,-1,-3,-2,2,0,3,0,-3,0,3,0,-2,-2,2,0,1,-3,2,-2,-2,2,0,2,1,-2,-3,-2,-1,0,...
>>> words.RandomWord(Integer(100), Integer(5), "abcde") # random results
>>> words.RandomWord(Integer(17), Integer(5), "abcde")     # random results

StandardEpisturmianWord(directive_word)[source]#

Returns the standard episturmian word (or epistandard word) directed by directive_word. Over a 2-letter alphabet, this function gives characteristic Sturmian words.

An infinite word $$w$$ over a finite alphabet $$A$$ is said to be standard episturmian (or epistandard) iff there exists an infinite word $$x_1x_2x_3\cdots$$ over $$A$$ (called the directive word of $$w$$) such that $$w$$ is the limit as $$n$$ goes to infinity of $$Pal(x_1\cdots x_n)$$, where $$Pal$$ is the iterated palindromic closure function.

Note that an infinite word is episturmian if it has the same set of factors as some epistandard word.

See for instance [DJP2001], [JP2002], and [GJ2007].

INPUT:

• directive_word – an infinite word or a period of a periodic infinite word

EXAMPLES:

sage: Fibonacci = words.StandardEpisturmianWord(Words('ab')('ab')); Fibonacci
word: abaababaabaababaababaabaababaabaababaaba...
sage: Tribonacci = words.StandardEpisturmianWord(Words('abc')('abc')); Tribonacci
word: abacabaabacababacabaabacabacabaabacababa...
word: aabaacaabaaabaacaabaabaacaabaaabaacaabaa...
sage: S = words.StandardEpisturmianWord(Fibonacci); S
word: abaabaababaabaabaababaabaababaabaabaabab...
sage: S[:25]
word: abaabaababaabaabaababaaba
sage: S = words.StandardEpisturmianWord(Tribonacci); S
word: abaabacabaabaabacabaababaabacabaabaabaca...
sage: words.StandardEpisturmianWord(123)
Traceback (most recent call last):
...
TypeError: directive_word is not a word, so it cannot be used to build an episturmian word
sage: words.StandardEpisturmianWord(Words('ab'))
Traceback (most recent call last):
...
TypeError: directive_word is not a word, so it cannot be used to build an episturmian word

>>> from sage.all import *
>>> Fibonacci = words.StandardEpisturmianWord(Words('ab')('ab')); Fibonacci
word: abaababaabaababaababaabaababaabaababaaba...
>>> Tribonacci = words.StandardEpisturmianWord(Words('abc')('abc')); Tribonacci
word: abacabaabacababacabaabacabacabaabacababa...
word: aabaacaabaaabaacaabaabaacaabaaabaacaabaa...
>>> S = words.StandardEpisturmianWord(Fibonacci); S
word: abaabaababaabaabaababaabaababaabaabaabab...
>>> S[:Integer(25)]
word: abaabaababaabaabaababaaba
>>> S = words.StandardEpisturmianWord(Tribonacci); S
word: abaabacabaabaabacabaababaabacabaabaabaca...
>>> words.StandardEpisturmianWord(Integer(123))
Traceback (most recent call last):
...
TypeError: directive_word is not a word, so it cannot be used to build an episturmian word
>>> words.StandardEpisturmianWord(Words('ab'))
Traceback (most recent call last):
...
TypeError: directive_word is not a word, so it cannot be used to build an episturmian word

ThueMorseWord(alphabet=(0, 1), base=2)[source]#

Returns the (Generalized) Thue-Morse word over the given alphabet.

There are several ways to define the Thue-Morse word $$t$$. We use the following definition: $$t[n]$$ is the sum modulo $$m$$ of the digits in the given base expansion of $$n$$.

See [BmBGL07], [Brlek89], and [MH38].

INPUT:

• alphabet – (default: (0, 1) ) any container that is suitable to build an instance of OrderedAlphabet (list, tuple, str, …)

• base – an integer (default : 2) greater or equal to 2

EXAMPLES:

Thue-Morse word:

sage: t = words.ThueMorseWord(); t
word: 0110100110010110100101100110100110010110...

>>> from sage.all import *
>>> t = words.ThueMorseWord(); t
word: 0110100110010110100101100110100110010110...


Thue-Morse word on other alphabets:

sage: t = words.ThueMorseWord('ab'); t
word: abbabaabbaababbabaababbaabbabaabbaababba...

>>> from sage.all import *
>>> t = words.ThueMorseWord('ab'); t
word: abbabaabbaababbabaababbaabbabaabbaababba...

sage: t = words.ThueMorseWord(['L1', 'L2'])
sage: t[:8]
word: L1,L2,L2,L1,L2,L1,L1,L2

>>> from sage.all import *
>>> t = words.ThueMorseWord(['L1', 'L2'])
>>> t[:Integer(8)]
word: L1,L2,L2,L1,L2,L1,L1,L2


Generalized Thue Morse word:

sage: words.ThueMorseWord(alphabet=(0,1,2), base=2)
word: 0112122012202001122020012001011212202001...
sage: t = words.ThueMorseWord(alphabet=(0,1,2), base=5); t
word: 0120112012201200120112012120122012001201...
sage: t[100:130].critical_exponent()
10/3

>>> from sage.all import *
>>> words.ThueMorseWord(alphabet=(Integer(0),Integer(1),Integer(2)), base=Integer(2))
word: 0112122012202001122020012001011212202001...
>>> t = words.ThueMorseWord(alphabet=(Integer(0),Integer(1),Integer(2)), base=Integer(5)); t
word: 0120112012201200120112012120122012001201...
>>> t[Integer(100):Integer(130)].critical_exponent()
10/3


REFERENCES:

[Brlek89]

Brlek, S. 1989. «Enumeration of the factors in the Thue-Morse word», Discrete Appl. Math., vol. 24, p. 83–96.

[MH38]

Morse, M., et G. A. Hedlund. 1938. «Symbolic dynamics», American Journal of Mathematics, vol. 60, p. 815–866.

UpperChristoffelWord(p, q, alphabet=(0, 1))[source]#

Returns the upper Christoffel word of slope $$p/q$$, where $$p$$ and $$q$$ are relatively prime non-negative integers, over the given alphabet.

The upper Christoffel word of slope p/q is equal to the reversal of the lower Christoffel word of slope $$p/q$$. Equivalently, if $$xuy$$ is the lower Christoffel word of slope $$p/q$$, where $$x$$ and $$y$$ are letters, then $$yux$$ is the upper Christoffel word of slope $$p/q$$ (because $$u$$ is a palindrome).

INPUT:

• alphabet – any container of length two that is suitable to build an instance of OrderedAlphabet (list, tuple, str, …)

EXAMPLES:

sage: words.UpperChristoffelWord(1,0)
word: 1

>>> from sage.all import *
>>> words.UpperChristoffelWord(Integer(1),Integer(0))
word: 1

sage: words.UpperChristoffelWord(0,1)
word: 0

>>> from sage.all import *
>>> words.UpperChristoffelWord(Integer(0),Integer(1))
word: 0

sage: words.UpperChristoffelWord(1,1)
word: 10

>>> from sage.all import *
>>> words.UpperChristoffelWord(Integer(1),Integer(1))
word: 10

sage: words.UpperChristoffelWord(4,7)
word: 10100100100

>>> from sage.all import *
>>> words.UpperChristoffelWord(Integer(4),Integer(7))
word: 10100100100

UpperMechanicalWord(alpha, rho=0, alphabet=None)[source]#

Returns the upper mechanical word with slope $$\alpha$$ and intercept $$\rho$$

The upper mechanical word $$s'_{\alpha,\rho}$$ with slope $$\alpha$$ and intercept $$\rho$$ is defined by $$s'_{\alpha,\rho}(n) = \lceil\alpha(n+1) + \rho\rceil - \lceil\alpha n + \rho\rceil$$. [Loth02]

INPUT:

• alpha – real number such that $$0 \leq\alpha\leq 1$$

• rho – real number (default: 0)

• alphabet – iterable of two elements or None (default: None)

OUTPUT:

infinite word

EXAMPLES:

sage: words.UpperMechanicalWord(1/golden_ratio^2)                           # needs sage.symbolic
word: 1010010100100101001010010010100100101001...
sage: words.UpperMechanicalWord(1/5)                                        # needs sage.symbolic
word: 1000010000100001000010000100001000010000...
sage: words.UpperMechanicalWord(1/pi)                                       # needs sage.symbolic
word: 1001001001001001001001000100100100100100...

>>> from sage.all import *
>>> words.UpperMechanicalWord(Integer(1)/golden_ratio**Integer(2))                           # needs sage.symbolic
word: 1010010100100101001010010010100100101001...
>>> words.UpperMechanicalWord(Integer(1)/Integer(5))                                        # needs sage.symbolic
word: 1000010000100001000010000100001000010000...
>>> words.UpperMechanicalWord(Integer(1)/pi)                                       # needs sage.symbolic
word: 1001001001001001001001000100100100100100...

dual_fibonacci_tile(n)[source]#

Returns the $$n$$-th dual Fibonacci Tile [BmBGL09].

EXAMPLES:

sage: for i in range(4): words.dual_fibonacci_tile(i)                       # needs sage.modules
Path: 3210
Path: 32123032301030121012
Path: 3212303230103230321232101232123032123210...
Path: 3212303230103230321232101232123032123210...

>>> from sage.all import *
>>> for i in range(Integer(4)): words.dual_fibonacci_tile(i)                       # needs sage.modules
Path: 3210
Path: 32123032301030121012
Path: 3212303230103230321232101232123032123210...
Path: 3212303230103230321232101232123032123210...

fibonacci_tile(n)[source]#

Returns the $$n$$-th Fibonacci Tile [BmBGL09].

EXAMPLES:

sage: for i in range(3): words.fibonacci_tile(i)                            # needs sage.modules
Path: 3210
Path: 323030101212
Path: 3230301030323212323032321210121232121010...

>>> from sage.all import *
>>> for i in range(Integer(3)): words.fibonacci_tile(i)                            # needs sage.modules
Path: 3210
Path: 323030101212
Path: 3230301030323212323032321210121232121010...


Returns the $$s$$-adic infinite word obtained from a sequence of morphisms applied on a letter.

DEFINITION (from [Fogg]):

Let $$w$$ be a infinite word over an alphabet $$A = A_0$$. A standard representation of $$w$$ is obtained from a sequence of substitutions $$\sigma_k : A_{k+1} \to A_k$$ and a sequence of letters $$a_k \in A_k$$ such that:

$\lim_{k\to\infty} \sigma_0 \circ \sigma_1 \circ \cdots \sigma_k(a_k).$

Given a set of substitutions $$S$$, we say that the representation is $$S$$-adic standard if the substitutions are chosen in $$S$$.

INPUT:

• sequence – An iterable sequence of indices or of morphisms. It may be finite or infinite. If sequence is infinite, the image of the $$(i+1)$$-th letter under the $$(i+1)$$-th morphism must start with the $$i$$-th letter.

• letters – A letter or a sequence of letters.

• morphisms – dict, list, callable or None (default: None) an object that maps indices to morphisms. If None, then sequence must consist of morphisms.

OUTPUT:

A word.

EXAMPLES:

Let us define three morphisms and compute the first nested successive prefixes of the $$s$$-adic word:

sage: m1 = WordMorphism('e->gh,f->hg')
sage: m2 = WordMorphism('c->ef,d->e')
sage: m3 = WordMorphism('a->cd,b->dc')
word: gh
word: ghhg
word: ghhggh

>>> from sage.all import *
>>> m1 = WordMorphism('e->gh,f->hg')
>>> m2 = WordMorphism('c->ef,d->e')
>>> m3 = WordMorphism('a->cd,b->dc')
word: gh
word: ghhg
word: ghhggh


When the given sequence of morphism is finite, one may simply give the last letter, i.e. 'a', instead of giving all of them, i.e. 'eca':

sage: words.s_adic([m1,m2,m3],'a')
word: ghhggh
word: ghghhg

>>> from sage.all import *
word: ghhggh
word: ghghhg


If the letters don’t satisfy the hypothesis of the algorithm (nested prefixes), an error is raised:

sage: words.s_adic([m1,m2,m3],'ecb')
Traceback (most recent call last):
...
ValueError: the hypothesis of the algorithm used is not satisfied; the image of the 3-th letter (=b) under the 3-th morphism (=a->cd, b->dc) should start with the 2-th letter (=c)

>>> from sage.all import *
Traceback (most recent call last):
...
ValueError: the hypothesis of the algorithm used is not satisfied; the image of the 3-th letter (=b) under the 3-th morphism (=a->cd, b->dc) should start with the 2-th letter (=c)


Let’s define the Thue-Morse morphism and the Fibonacci morphism which will be used below to illustrate more examples and let’s import the repeat tool from the itertools:

sage: tm = WordMorphism('a->ab,b->ba')
sage: fib = WordMorphism('a->ab,b->a')
sage: from itertools import repeat

>>> from sage.all import *
>>> tm = WordMorphism('a->ab,b->ba')
>>> fib = WordMorphism('a->ab,b->a')
>>> from itertools import repeat


Two trivial examples of infinite $$s$$-adic words:

sage: words.s_adic(repeat(tm),repeat('a'))
word: abbabaabbaababbabaababbaabbabaabbaababba...

>>> from sage.all import *
word: abbabaabbaababbabaababbaabbabaabbaababba...

sage: words.s_adic(repeat(fib),repeat('a'))
word: abaababaabaababaababaabaababaabaababaaba...

>>> from sage.all import *
word: abaababaabaababaababaabaababaabaababaaba...


A less trivial infinite $$s$$-adic word:

sage: D = {4:tm,5:fib}
sage: tmword = words.ThueMorseWord([4,5])
sage: it = (D[a] for a in tmword)
word: abbaababbaabbaabbaababbaababbaabbaababba...

>>> from sage.all import *
>>> D = {Integer(4):tm,Integer(5):fib}
>>> tmword = words.ThueMorseWord([Integer(4),Integer(5)])
>>> it = (D[a] for a in tmword)
word: abbaababbaabbaabbaababbaababbaabbaababba...


The same thing using a sequence of indices:

sage: tmword = words.ThueMorseWord([0,1])
word: abbaababbaabbaabbaababbaababbaabbaababba...

>>> from sage.all import *
>>> tmword = words.ThueMorseWord([Integer(0),Integer(1)])
word: abbaababbaabbaabbaababbaababbaabbaababba...


The correspondence of the indices may be given as a dict:

sage: words.s_adic(tmword, repeat('a'), {0:tm,1:fib})
word: abbaababbaabbaabbaababbaababbaabbaababba...

>>> from sage.all import *
word: abbaababbaabbaabbaababbaababbaabbaababba...


because dict are more versatile for indices:

sage: tmwordTF = words.ThueMorseWord('TF')
word: abbaababbaabbaabbaababbaababbaabbaababba...

>>> from sage.all import *
>>> tmwordTF = words.ThueMorseWord('TF')
word: abbaababbaabbaabbaababbaababbaabbaababba...


or by a callable:

sage: f = lambda n: tm if n == 0 else fib
word: abbaababbaabbaabbaababbaababbaabbaababba...

>>> from sage.all import *
>>> f = lambda n: tm if n == Integer(0) else fib
word: abbaababbaabbaabbaababbaababbaabbaababba...


Random infinite $$s$$-adic words:

sage: from sage.misc.prandom import randint
sage: def it():
....:   while True: yield randint(0,1)
sage: words.s_adic(it(), repeat('a'), [tm,fib])  # random
word: abbaabababbaababbaabbaababbaabababbaabba...
sage: words.s_adic(it(), repeat('a'), [tm,fib])  # random
word: abbaababbaabbaababbaababbaabbaababbaabba...
sage: words.s_adic(it(), repeat('a'), [tm,fib])  # random
word: abaaababaabaabaaababaabaaababaaababaabaa...

>>> from sage.all import *
>>> from sage.misc.prandom import randint
>>> def it():
...   while True: yield randint(Integer(0),Integer(1))
>>> words.s_adic(it(), repeat('a'), [tm,fib])  # random
word: abbaabababbaababbaabbaababbaabababbaabba...
>>> words.s_adic(it(), repeat('a'), [tm,fib])  # random
word: abbaababbaabbaababbaababbaabbaababbaabba...
>>> words.s_adic(it(), repeat('a'), [tm,fib])  # random
word: abaaababaabaabaaababaabaaababaaababaabaa...


An example where the sequences cycle on two morphisms and two letters:

sage: G = WordMorphism('a->cd,b->dc')
sage: H = WordMorphism('c->ab,d->ba')
sage: from itertools import cycle
word: cddc
word: cddcdccddccdcddcdccdcddccddcdccddccdcddc...

>>> from sage.all import *
>>> G = WordMorphism('a->cd,b->dc')
>>> H = WordMorphism('c->ab,d->ba')
>>> from itertools import cycle
word: cddc
word: cddcdccddccdcddcdccdcddccddcdccddccdcddc...


The morphism $$\sigma: a\mapsto ba, b\mapsto b$$ can’t satisfy the hypothesis of the nested prefixes, but one may compute arbitrarily long finite words having the limit $$\sigma^\omega(a)$$:

sage: sigma = WordMorphism('a->ba,b->b')
Traceback (most recent call last):
...
ValueError: the hypothesis of the algorithm used is not satisfied; the image of the 2-th letter (=a) under the 2-th morphism (=a->ba, b->b) should start with the 1-th letter (=a)
word: ba
word: bba
word: bbba
word: bbbba
word: bbbbba
word: bbbbbba
word: bbbbbbba

>>> from sage.all import *
>>> sigma = WordMorphism('a->ba,b->b')
Traceback (most recent call last):
...
ValueError: the hypothesis of the algorithm used is not satisfied; the image of the 2-th letter (=a) under the 2-th morphism (=a->ba, b->b) should start with the 1-th letter (=a)
word: ba
word: bba
word: bbba
word: bbbba
word: bbbbba
word: bbbbbba
word: bbbbbbba


The following examples illustrates an $$S$$-adic word defined over an infinite set $$S$$ of morphisms $$x_h$$:

sage: x = lambda h:WordMorphism({1:[2],2:[3]+[1]*(h+1),3:[3]+[1]*h})
sage: for h in [0,1,2,3]:
....:     print("{} {}".format(h, x(h)))
0 1->2, 2->31, 3->3
1 1->2, 2->311, 3->31
2 1->2, 2->3111, 3->311
3 1->2, 2->31111, 3->3111
sage: w = Word(lambda n : valuation(n+1, 2) ); w
word: 0102010301020104010201030102010501020103...
sage: s = words.s_adic(w, repeat(3), x); s
word: 3232232232322322322323223223232232232232...
sage: prefixe = s[:10000]
sage: list(map(prefixe.number_of_factors, range(15)))
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
sage: [_[i+1] - _[i] for i in range(len(_)-1)]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

>>> from sage.all import *
>>> x = lambda h:WordMorphism({Integer(1):[Integer(2)],Integer(2):[Integer(3)]+[Integer(1)]*(h+Integer(1)),Integer(3):[Integer(3)]+[Integer(1)]*h})
>>> for h in [Integer(0),Integer(1),Integer(2),Integer(3)]:
...     print("{} {}".format(h, x(h)))
0 1->2, 2->31, 3->3
1 1->2, 2->311, 3->31
2 1->2, 2->3111, 3->311
3 1->2, 2->31111, 3->3111
>>> w = Word(lambda n : valuation(n+Integer(1), Integer(2)) ); w
word: 0102010301020104010201030102010501020103...
>>> s = words.s_adic(w, repeat(Integer(3)), x); s
word: 3232232232322322322323223223232232232232...
>>> prefixe = s[:Integer(10000)]
>>> list(map(prefixe.number_of_factors, range(Integer(15))))
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
>>> [_[i+Integer(1)] - _[i] for i in range(len(_)-Integer(1))]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]


AUTHORS:

• Sébastien Labbé (2009-12-18): initial version