Abstract word (finite or infinite)

This module gathers functions that works for both finite and infinite words.

AUTHORS:

  • Sébastien Labbé

  • Franco Saliola

EXAMPLES:

sage: a = 0.618
sage: g = words.CodingOfRotationWord(alpha=a, beta=1-a, x=a)
sage: f = words.FibonacciWord()
sage: p = f.longest_common_prefix(g, length='finite')
sage: p
word: 0100101001001010010100100101001001010010...
sage: p.length()
231

>>> from sage.all import *
>>> a = RealNumber('0.618')
>>> g = words.CodingOfRotationWord(alpha=a, beta=Integer(1)-a, x=a)
>>> f = words.FibonacciWord()
>>> p = f.longest_common_prefix(g, length='finite')
>>> p
word: 0100101001001010010100100101001001010010...
>>> p.length()
231
class sage.combinat.words.abstract_word.Word_class[source]

Bases: SageObject

apply_morphism(morphism)[source]

Return the word obtained by applying the morphism to self.

INPUT:

  • morphism – can be an instance of WordMorphism, or anything that can be used to construct one

EXAMPLES:

sage: w = Word("ab")
sage: d = {'a':'ab', 'b':'ba'}
sage: w.apply_morphism(d)
word: abba
sage: w.apply_morphism(WordMorphism(d))
word: abba

>>> from sage.all import *
>>> w = Word("ab")
>>> d = {'a':'ab', 'b':'ba'}
>>> w.apply_morphism(d)
word: abba
>>> w.apply_morphism(WordMorphism(d))
word: abba


sage: w = Word('ababa')
sage: d = dict(a='ab', b='ba')
sage: d
{'a': 'ab', 'b': 'ba'}
sage: w.apply_morphism(d)
word: abbaabbaab

>>> from sage.all import *
>>> w = Word('ababa')
>>> d = dict(a='ab', b='ba')
>>> d
{'a': 'ab', 'b': 'ba'}
>>> w.apply_morphism(d)
word: abbaabbaab

For infinite words:

sage: t = words.ThueMorseWord([0,1]); t
word: 0110100110010110100101100110100110010110...
sage: t.apply_morphism({0:8,1:9})
word: 8998988998898998988989988998988998898998...

>>> from sage.all import *
>>> t = words.ThueMorseWord([Integer(0),Integer(1)]); t
word: 0110100110010110100101100110100110010110...
>>> t.apply_morphism({Integer(0):Integer(8),Integer(1):Integer(9)})
word: 8998988998898998988989988998988998898998...
complete_return_words_iterator(fact)[source]

Return an iterator over all the complete return words of fact in self (without unicity).

A complete return words \(u\) of a factor \(v\) is a factor starting by the given factor \(v\) and ending just after the next occurrence of this factor \(v\). See for instance [1].

INPUT:

  • fact – a non empty finite word

OUTPUT: iterator

EXAMPLES:

sage: TM = words.ThueMorseWord()
sage: fact = Word([0,1,1,0,1])
sage: it = TM.complete_return_words_iterator(fact)
sage: next(it)
word: 01101001100101101
sage: next(it)
word: 01101001011001101
sage: next(it)
word: 011010011001011001101
sage: next(it)
word: 0110100101101
sage: next(it)
word: 01101001100101101
sage: next(it)
word: 01101001011001101

>>> from sage.all import *
>>> TM = words.ThueMorseWord()
>>> fact = Word([Integer(0),Integer(1),Integer(1),Integer(0),Integer(1)])
>>> it = TM.complete_return_words_iterator(fact)
>>> next(it)
word: 01101001100101101
>>> next(it)
word: 01101001011001101
>>> next(it)
word: 011010011001011001101
>>> next(it)
word: 0110100101101
>>> next(it)
word: 01101001100101101
>>> next(it)
word: 01101001011001101

REFERENCES:

  • [1] J. Justin, L. Vuillon, Return words in Sturmian and episturmian words, Theor. Inform. Appl. 34 (2000) 343–356.

delta()[source]

Return the image of self under the delta morphism.

This is the word composed of the length of consecutive runs of the same letter in a given word.

OUTPUT: word over integers

EXAMPLES:

For finite words:

sage: W = Words('0123456789')
sage: W('22112122').delta()
word: 22112
sage: W('555008').delta()
word: 321
sage: W().delta()
word:
sage: Word('aabbabaa').delta()
word: 22112

>>> from sage.all import *
>>> W = Words('0123456789')
>>> W('22112122').delta()
word: 22112
>>> W('555008').delta()
word: 321
>>> W().delta()
word:
>>> Word('aabbabaa').delta()
word: 22112

For infinite words:

sage: t = words.ThueMorseWord()
sage: t.delta()
word: 1211222112112112221122211222112112112221...

>>> from sage.all import *
>>> t = words.ThueMorseWord()
>>> t.delta()
word: 1211222112112112221122211222112112112221...
factor_occurrences_iterator(fact)[source]

Return an iterator over all occurrences (including overlapping ones) of fact in self in their order of appearance.

INPUT:

  • fact – a non empty finite word

OUTPUT: iterator

EXAMPLES:

sage: TM = words.ThueMorseWord()
sage: fact = Word([0,1,1,0,1])
sage: it = TM.factor_occurrences_iterator(fact)
sage: next(it)
0
sage: next(it)
12
sage: next(it)
24

>>> from sage.all import *
>>> TM = words.ThueMorseWord()
>>> fact = Word([Integer(0),Integer(1),Integer(1),Integer(0),Integer(1)])
>>> it = TM.factor_occurrences_iterator(fact)
>>> next(it)
0
>>> next(it)
12
>>> next(it)
24


sage: u = Word('121')
sage: w = Word('121213211213')
sage: list(w.factor_occurrences_iterator(u))
[0, 2, 8]

>>> from sage.all import *
>>> u = Word('121')
>>> w = Word('121213211213')
>>> list(w.factor_occurrences_iterator(u))
[0, 2, 8]
finite_differences(mod=None)[source]

Return the word obtained by the differences of consecutive letters of self.

INPUT:

  • self – a word over the integers

  • mod – (default: None) it can be one of the following:

    • None or 0 : result is over the integers

    • integer : result is over the integers modulo mod.

EXAMPLES:

sage: w = Word([x^2 for x in range(10)])
sage: w.finite_differences()
word: 1,3,5,7,9,11,13,15,17
sage: w.finite_differences(mod=4)
word: 131313131
sage: w.finite_differences(mod=0)
word: 1,3,5,7,9,11,13,15,17

>>> from sage.all import *
>>> w = Word([x**Integer(2) for x in range(Integer(10))])
>>> w.finite_differences()
word: 1,3,5,7,9,11,13,15,17
>>> w.finite_differences(mod=Integer(4))
word: 131313131
>>> w.finite_differences(mod=Integer(0))
word: 1,3,5,7,9,11,13,15,17
first_occurrence(other, start=0)[source]

Return the position of the first occurrence of other in self.

If other is not a factor of self, it returns None or loops forever when self is an infinite word.

INPUT:

  • other – a finite word

  • start – integer (default: \(0\)) where the search starts

OUTPUT: integer or None

EXAMPLES:

sage: w = Word('01234567890123456789')
sage: w.first_occurrence(Word('3456'))
3
sage: w.first_occurrence(Word('3456'), start=7)
13

>>> from sage.all import *
>>> w = Word('01234567890123456789')
>>> w.first_occurrence(Word('3456'))
3
>>> w.first_occurrence(Word('3456'), start=Integer(7))
13

When the factor is not present, None is returned:

sage: w.first_occurrence(Word('3456'), start=17) is None
True
sage: w.first_occurrence(Word('3333')) is None
True

>>> from sage.all import *
>>> w.first_occurrence(Word('3456'), start=Integer(17)) is None
True
>>> w.first_occurrence(Word('3333')) is None
True

Also works for searching a finite word in an infinite word:

sage: w = Word('0123456789')^oo
sage: w.first_occurrence(Word('3456'))
3
sage: w.first_occurrence(Word('3456'), start=1000)
1003

>>> from sage.all import *
>>> w = Word('0123456789')**oo
>>> w.first_occurrence(Word('3456'))
3
>>> w.first_occurrence(Word('3456'), start=Integer(1000))
1003

But it will loop for ever if the factor is not found:

sage: w.first_occurrence(Word('3333')) # not tested -- infinite loop

>>> from sage.all import *
>>> w.first_occurrence(Word('3333')) # not tested -- infinite loop

The empty word occurs in a word:

sage: Word('123').first_occurrence(Word(''), 0)
0
sage: Word('').first_occurrence(Word(''), 0)
0

>>> from sage.all import *
>>> Word('123').first_occurrence(Word(''), Integer(0))
0
>>> Word('').first_occurrence(Word(''), Integer(0))
0
is_empty()[source]

Return True if the length of self is zero, and False otherwise.

EXAMPLES:

sage: it = iter([])
sage: Word(it).is_empty()
True
sage: it = iter([1,2,3])
sage: Word(it).is_empty()
False
sage: from itertools import count
sage: Word(count()).is_empty()
False

>>> from sage.all import *
>>> it = iter([])
>>> Word(it).is_empty()
True
>>> it = iter([Integer(1),Integer(2),Integer(3)])
>>> Word(it).is_empty()
False
>>> from itertools import count
>>> Word(count()).is_empty()
False
is_finite()[source]

Return whether this word is known to be finite.

Warning

A word defined by an iterator such that its end has never been reached will returns False.

EXAMPLES:

sage: Word([]).is_finite()
True
sage: Word('a').is_finite()
True
sage: TM = words.ThueMorseWord()
sage: TM.is_finite()
False

>>> from sage.all import *
>>> Word([]).is_finite()
True
>>> Word('a').is_finite()
True
>>> TM = words.ThueMorseWord()
>>> TM.is_finite()
False


sage: w = Word(iter('a'*100))
sage: w.is_finite()
False

>>> from sage.all import *
>>> w = Word(iter('a'*Integer(100)))
>>> w.is_finite()
False
iterated_right_palindromic_closure(f=None, algorithm='recursive')[source]

Return the iterated (\(f\)-)palindromic closure of self.

INPUT:

  • f – involution (default: None) on the alphabet of self; it must be callable on letters as well as words (e.g. WordMorphism)

  • algorithm – string (default: 'recursive'); specifying which algorithm to be used when computing the iterated palindromic closure. It must be one of the two following values:

    • 'definition' – computed using the definition

    • 'recursive' – computation based on an efficient formula that recursively computes the iterated right palindromic closure without having to recompute the longest \(f\)-palindromic suffix at each iteration [2].

OUTPUT: word; the iterated (\(f\)-)palindromic closure of self

EXAMPLES:

sage: Word('123').iterated_right_palindromic_closure()
word: 1213121

>>> from sage.all import *
>>> Word('123').iterated_right_palindromic_closure()
word: 1213121


sage: w = Word('abc')
sage: w.iterated_right_palindromic_closure()
word: abacaba

>>> from sage.all import *
>>> w = Word('abc')
>>> w.iterated_right_palindromic_closure()
word: abacaba


sage: w = Word('aaa')
sage: w.iterated_right_palindromic_closure()
word: aaa

>>> from sage.all import *
>>> w = Word('aaa')
>>> w.iterated_right_palindromic_closure()
word: aaa


sage: w = Word('abbab')
sage: w.iterated_right_palindromic_closure()
word: ababaabababaababa

>>> from sage.all import *
>>> w = Word('abbab')
>>> w.iterated_right_palindromic_closure()
word: ababaabababaababa

A right \(f\)-palindromic closure:

sage: f = WordMorphism('a->b,b->a')
sage: w = Word('abbab')
sage: w.iterated_right_palindromic_closure(f=f)
word: abbaabbaababbaabbaabbaababbaabbaab

>>> from sage.all import *
>>> f = WordMorphism('a->b,b->a')
>>> w = Word('abbab')
>>> w.iterated_right_palindromic_closure(f=f)
word: abbaabbaababbaabbaabbaababbaabbaab

An infinite word:

sage: t = words.ThueMorseWord('ab')
sage: t.iterated_right_palindromic_closure()
word: ababaabababaababaabababaababaabababaabab...

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

There are two implementations computing the iterated right \(f\)-palindromic closure, the latter being much more efficient:

sage: w = Word('abaab')
sage: u = w.iterated_right_palindromic_closure(algorithm='definition')
sage: v = w.iterated_right_palindromic_closure(algorithm='recursive')
sage: u
word: abaabaababaabaaba
sage: u == v
True
sage: w = words.RandomWord(8)
sage: u = w.iterated_right_palindromic_closure(algorithm='definition')
sage: v = w.iterated_right_palindromic_closure(algorithm='recursive')
sage: u == v
True

>>> from sage.all import *
>>> w = Word('abaab')
>>> u = w.iterated_right_palindromic_closure(algorithm='definition')
>>> v = w.iterated_right_palindromic_closure(algorithm='recursive')
>>> u
word: abaabaababaabaaba
>>> u == v
True
>>> w = words.RandomWord(Integer(8))
>>> u = w.iterated_right_palindromic_closure(algorithm='definition')
>>> v = w.iterated_right_palindromic_closure(algorithm='recursive')
>>> u == v
True

REFERENCES:

  • [1] A. de Luca, A. De Luca, Pseudopalindrome closure operators in free monoids, Theoret. Comput. Sci. 362 (2006) 282–300.

  • [2] J. Justin, Episturmian morphisms and a Galois theorem on continued fractions, RAIRO Theoret. Informatics Appl. 39 (2005) 207-215.

length()[source]

Return the length of self.

lex_greater(other)[source]

Return True if self is lexicographically greater than other.

EXAMPLES:

sage: w = Word([1,2,3])
sage: u = Word([1,3,2])
sage: v = Word([3,2,1])
sage: w.lex_greater(u)
False
sage: v.lex_greater(w)
True
sage: a = Word("abba")
sage: b = Word("abbb")
sage: a.lex_greater(b)
False
sage: b.lex_greater(a)
True

>>> from sage.all import *
>>> w = Word([Integer(1),Integer(2),Integer(3)])
>>> u = Word([Integer(1),Integer(3),Integer(2)])
>>> v = Word([Integer(3),Integer(2),Integer(1)])
>>> w.lex_greater(u)
False
>>> v.lex_greater(w)
True
>>> a = Word("abba")
>>> b = Word("abbb")
>>> a.lex_greater(b)
False
>>> b.lex_greater(a)
True

For infinite words:

sage: t = words.ThueMorseWord()
sage: t[:10].lex_greater(t)
False
sage: t.lex_greater(t[:10])
True

>>> from sage.all import *
>>> t = words.ThueMorseWord()
>>> t[:Integer(10)].lex_greater(t)
False
>>> t.lex_greater(t[:Integer(10)])
True
lex_less(other)[source]

Return True if self is lexicographically less than other.

EXAMPLES:

sage: w = Word([1,2,3])
sage: u = Word([1,3,2])
sage: v = Word([3,2,1])
sage: w.lex_less(u)
True
sage: v.lex_less(w)
False
sage: a = Word("abba")
sage: b = Word("abbb")
sage: a.lex_less(b)
True
sage: b.lex_less(a)
False

>>> from sage.all import *
>>> w = Word([Integer(1),Integer(2),Integer(3)])
>>> u = Word([Integer(1),Integer(3),Integer(2)])
>>> v = Word([Integer(3),Integer(2),Integer(1)])
>>> w.lex_less(u)
True
>>> v.lex_less(w)
False
>>> a = Word("abba")
>>> b = Word("abbb")
>>> a.lex_less(b)
True
>>> b.lex_less(a)
False

For infinite words:

sage: t = words.ThueMorseWord()
sage: t.lex_less(t[:10])
False
sage: t[:10].lex_less(t)
True

>>> from sage.all import *
>>> t = words.ThueMorseWord()
>>> t.lex_less(t[:Integer(10)])
False
>>> t[:Integer(10)].lex_less(t)
True
longest_common_prefix(other, length='unknown')[source]

Return the longest common prefix of self and other.

INPUT:

  • other – word

  • length – string (default: 'unknown') the length type of the resulting word if known. It may be one of the following:

    • 'unknown'

    • 'finite'

    • 'infinite'

EXAMPLES:

sage: f = lambda n : add(Integer(n).digits(2)) % 2
sage: t = Word(f)
sage: u = t[:10]
sage: t.longest_common_prefix(u)
word: 0110100110

>>> from sage.all import *
>>> f = lambda n : add(Integer(n).digits(Integer(2))) % Integer(2)
>>> t = Word(f)
>>> u = t[:Integer(10)]
>>> t.longest_common_prefix(u)
word: 0110100110

The longest common prefix of two equal infinite words:

sage: t1 = Word(f)
sage: t2 = Word(f)
sage: t1.longest_common_prefix(t2)
word: 0110100110010110100101100110100110010110...

>>> from sage.all import *
>>> t1 = Word(f)
>>> t2 = Word(f)
>>> t1.longest_common_prefix(t2)
word: 0110100110010110100101100110100110010110...

Useful to study the approximation of an infinite word:

sage: a = 0.618
sage: g = words.CodingOfRotationWord(alpha=a, beta=1-a, x=a)
sage: f = words.FibonacciWord()
sage: p = f.longest_common_prefix(g, length='finite')
sage: p.length()
231

>>> from sage.all import *
>>> a = RealNumber('0.618')
>>> g = words.CodingOfRotationWord(alpha=a, beta=Integer(1)-a, x=a)
>>> f = words.FibonacciWord()
>>> p = f.longest_common_prefix(g, length='finite')
>>> p.length()
231
longest_periodic_prefix(period=1)[source]

Return the longest prefix of self having the given period.

INPUT:

  • period – positive integer (default: 1)

OUTPUT: word

EXAMPLES:

sage: Word([]).longest_periodic_prefix()
word:
sage: Word([1]).longest_periodic_prefix()
word: 1
sage: Word([1,2]).longest_periodic_prefix()
word: 1
sage: Word([1,1,2]).longest_periodic_prefix()
word: 11
sage: Word([1,2,1,2,1,3]).longest_periodic_prefix(2)
word: 12121
sage: type(_)
<class 'sage.combinat.words.word.FiniteWord_iter_with_caching'>
sage: Word(lambda n:0).longest_periodic_prefix()
word: 0000000000000000000000000000000000000000...

>>> from sage.all import *
>>> Word([]).longest_periodic_prefix()
word:
>>> Word([Integer(1)]).longest_periodic_prefix()
word: 1
>>> Word([Integer(1),Integer(2)]).longest_periodic_prefix()
word: 1
>>> Word([Integer(1),Integer(1),Integer(2)]).longest_periodic_prefix()
word: 11
>>> Word([Integer(1),Integer(2),Integer(1),Integer(2),Integer(1),Integer(3)]).longest_periodic_prefix(Integer(2))
word: 12121
>>> type(_)
<class 'sage.combinat.words.word.FiniteWord_iter_with_caching'>
>>> Word(lambda n:Integer(0)).longest_periodic_prefix()
word: 0000000000000000000000000000000000000000...
palindrome_prefixes_iterator(max_length=None)[source]

Return an iterator over the palindrome prefixes of self.

INPUT:

  • max_length – nonnegative integer or None (default); the maximum length of the prefixes

OUTPUT: iterator

EXAMPLES:

sage: w = Word('abaaba')
sage: for pp in w.palindrome_prefixes_iterator(): pp
word:
word: a
word: aba
word: abaaba
sage: for pp in w.palindrome_prefixes_iterator(max_length=4): pp
word:
word: a
word: aba

>>> from sage.all import *
>>> w = Word('abaaba')
>>> for pp in w.palindrome_prefixes_iterator(): pp
word:
word: a
word: aba
word: abaaba
>>> for pp in w.palindrome_prefixes_iterator(max_length=Integer(4)): pp
word:
word: a
word: aba

You can iterate over the palindrome prefixes of an infinite word:

sage: f = words.FibonacciWord()
sage: for pp in f.palindrome_prefixes_iterator(max_length=20): pp
word:
word: 0
word: 010
word: 010010
word: 01001010010
word: 0100101001001010010

>>> from sage.all import *
>>> f = words.FibonacciWord()
>>> for pp in f.palindrome_prefixes_iterator(max_length=Integer(20)): pp
word:
word: 0
word: 010
word: 010010
word: 01001010010
word: 0100101001001010010
parent()[source]

Return the parent of self.

partial_sums(start, mod=None)[source]

Return the word defined by the partial sums of its prefixes.

INPUT:

  • self – a word over the integers

  • start – integer; the first letter of the resulting word

  • mod – (default: None) it can be one of the following:

    • None or 0 : result is over the integers

    • integer : result is over the integers modulo mod.

EXAMPLES:

sage: w = Word(range(10))
sage: w.partial_sums(0)
word: 0,0,1,3,6,10,15,21,28,36,45
sage: w.partial_sums(1)
word: 1,1,2,4,7,11,16,22,29,37,46

>>> from sage.all import *
>>> w = Word(range(Integer(10)))
>>> w.partial_sums(Integer(0))
word: 0,0,1,3,6,10,15,21,28,36,45
>>> w.partial_sums(Integer(1))
word: 1,1,2,4,7,11,16,22,29,37,46


sage: w = Word([1,2,3,1,2,3,2,2,2,2])
sage: w.partial_sums(0, mod=None)
word: 0,1,3,6,7,9,12,14,16,18,20
sage: w.partial_sums(0, mod=0)
word: 0,1,3,6,7,9,12,14,16,18,20
sage: w.partial_sums(0, mod=8)
word: 01367146024
sage: w.partial_sums(0, mod=4)
word: 01323102020
sage: w.partial_sums(0, mod=2)
word: 01101100000
sage: w.partial_sums(0, mod=1)
word: 00000000000

>>> from sage.all import *
>>> w = Word([Integer(1),Integer(2),Integer(3),Integer(1),Integer(2),Integer(3),Integer(2),Integer(2),Integer(2),Integer(2)])
>>> w.partial_sums(Integer(0), mod=None)
word: 0,1,3,6,7,9,12,14,16,18,20
>>> w.partial_sums(Integer(0), mod=Integer(0))
word: 0,1,3,6,7,9,12,14,16,18,20
>>> w.partial_sums(Integer(0), mod=Integer(8))
word: 01367146024
>>> w.partial_sums(Integer(0), mod=Integer(4))
word: 01323102020
>>> w.partial_sums(Integer(0), mod=Integer(2))
word: 01101100000
>>> w.partial_sums(Integer(0), mod=Integer(1))
word: 00000000000
prefixes_iterator(max_length=None)[source]

Return an iterator over the prefixes of self.

INPUT:

  • max_length – nonnegative integer or None (default); the maximum length of the prefixes

OUTPUT: iterator

EXAMPLES:

sage: w = Word('abaaba')
sage: for p in w.prefixes_iterator(): p
word:
word: a
word: ab
word: aba
word: abaa
word: abaab
word: abaaba
sage: for p in w.prefixes_iterator(max_length=3): p
word:
word: a
word: ab
word: aba

>>> from sage.all import *
>>> w = Word('abaaba')
>>> for p in w.prefixes_iterator(): p
word:
word: a
word: ab
word: aba
word: abaa
word: abaab
word: abaaba
>>> for p in w.prefixes_iterator(max_length=Integer(3)): p
word:
word: a
word: ab
word: aba

You can iterate over the prefixes of an infinite word:

sage: f = words.FibonacciWord()
sage: for p in f.prefixes_iterator(max_length=8): p
word:
word: 0
word: 01
word: 010
word: 0100
word: 01001
word: 010010
word: 0100101
word: 01001010

>>> from sage.all import *
>>> f = words.FibonacciWord()
>>> for p in f.prefixes_iterator(max_length=Integer(8)): p
word:
word: 0
word: 01
word: 010
word: 0100
word: 01001
word: 010010
word: 0100101
word: 01001010
return_words_iterator(fact)[source]

Return an iterator over all the return words of fact in self (without unicity).

INPUT:

  • fact – a non empty finite word

OUTPUT: iterator

EXAMPLES:

sage: w = Word('baccabccbacbca')
sage: b = Word('b')
sage: list(w.return_words_iterator(b))
[word: bacca, word: bcc, word: bac]

>>> from sage.all import *
>>> w = Word('baccabccbacbca')
>>> b = Word('b')
>>> list(w.return_words_iterator(b))
[word: bacca, word: bcc, word: bac]


sage: TM = words.ThueMorseWord()
sage: fact = Word([0,1,1,0,1])
sage: it = TM.return_words_iterator(fact)
sage: next(it)
word: 011010011001
sage: next(it)
word: 011010010110
sage: next(it)
word: 0110100110010110
sage: next(it)
word: 01101001
sage: next(it)
word: 011010011001
sage: next(it)
word: 011010010110

>>> from sage.all import *
>>> TM = words.ThueMorseWord()
>>> fact = Word([Integer(0),Integer(1),Integer(1),Integer(0),Integer(1)])
>>> it = TM.return_words_iterator(fact)
>>> next(it)
word: 011010011001
>>> next(it)
word: 011010010110
>>> next(it)
word: 0110100110010110
>>> next(it)
word: 01101001
>>> next(it)
word: 011010011001
>>> next(it)
word: 011010010110
string_rep()[source]

Return the (truncated) raw sequence of letters as a string.

EXAMPLES:

sage: Word('abbabaab').string_rep()
'abbabaab'
sage: Word([0, 1, 0, 0, 1]).string_rep()
'01001'
sage: Word([0,1,10,101]).string_rep()
'0,1,10,101'
sage: WordOptions(letter_separator='-')
sage: Word([0,1,10,101]).string_rep()
'0-1-10-101'
sage: WordOptions(letter_separator=',')

>>> from sage.all import *
>>> Word('abbabaab').string_rep()
'abbabaab'
>>> Word([Integer(0), Integer(1), Integer(0), Integer(0), Integer(1)]).string_rep()
'01001'
>>> Word([Integer(0),Integer(1),Integer(10),Integer(101)]).string_rep()
'0,1,10,101'
>>> WordOptions(letter_separator='-')
>>> Word([Integer(0),Integer(1),Integer(10),Integer(101)]).string_rep()
'0-1-10-101'
>>> WordOptions(letter_separator=',')
sum_digits(base=2, mod=None)[source]

Return the sequence of the sum modulo mod of the digits written in base base of self.

INPUT:

  • self – word over natural numbers

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

  • mod – modulo (default: None); can take the following values: - integer – the modulo - None – the value base is considered for the modulo

EXAMPLES:

The Thue-Morse word:

sage: from itertools import count
sage: Word(count()).sum_digits()
word: 0110100110010110100101100110100110010110...

>>> from sage.all import *
>>> from itertools import count
>>> Word(count()).sum_digits()
word: 0110100110010110100101100110100110010110...

Sum of digits modulo 2 of the prime numbers written in base 2:

sage: Word(primes(1000)).sum_digits()                                       # needs sage.libs.pari
word: 1001110100111010111011001011101110011011...

>>> from sage.all import *
>>> Word(primes(Integer(1000))).sum_digits()                                       # needs sage.libs.pari
word: 1001110100111010111011001011101110011011...

Sum of digits modulo 3 of the prime numbers written in base 3:

sage: Word(primes(1000)).sum_digits(base=3)                                 # needs sage.libs.pari
word: 2100002020002221222121022221022122111022...
sage: Word(primes(1000)).sum_digits(base=3, mod=3)                          # needs sage.libs.pari
word: 2100002020002221222121022221022122111022...

>>> from sage.all import *
>>> Word(primes(Integer(1000))).sum_digits(base=Integer(3))                                 # needs sage.libs.pari
word: 2100002020002221222121022221022122111022...
>>> Word(primes(Integer(1000))).sum_digits(base=Integer(3), mod=Integer(3))                          # needs sage.libs.pari
word: 2100002020002221222121022221022122111022...

Sum of digits modulo 2 of the prime numbers written in base 3:

sage: Word(primes(1000)).sum_digits(base=3, mod=2)                          # needs sage.libs.pari
word: 0111111111111111111111111111111111111111...

>>> from sage.all import *
>>> Word(primes(Integer(1000))).sum_digits(base=Integer(3), mod=Integer(2))                          # needs sage.libs.pari
word: 0111111111111111111111111111111111111111...

Sum of digits modulo 7 of the prime numbers written in base 10:

sage: Word(primes(1000)).sum_digits(base=10, mod=7)                         # needs sage.libs.pari
word: 2350241354435041006132432241353546006304...

>>> from sage.all import *
>>> Word(primes(Integer(1000))).sum_digits(base=Integer(10), mod=Integer(7))                         # needs sage.libs.pari
word: 2350241354435041006132432241353546006304...

Negative entries:

sage: w = Word([-1,0,1,2,3,4,5])
sage: w.sum_digits()
Traceback (most recent call last):
...
NotImplementedError: nth digit of Thue-Morse word is not implemented for negative value of n

>>> from sage.all import *
>>> w = Word([-Integer(1),Integer(0),Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)])
>>> w.sum_digits()
Traceback (most recent call last):
...
NotImplementedError: nth digit of Thue-Morse word is not implemented for negative value of n
to_integer_word()[source]

Return a word over the integers whose letters are those output by self._to_integer_iterator()

EXAMPLES:

sage: from itertools import count
sage: w = Word(count()); w
word: 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,...
sage: w.to_integer_word()
word: 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,...
sage: w = Word(iter("abbacabba"), length='finite'); w
word: abbacabba
sage: w.to_integer_word()
word: 011020110
sage: w = Word(iter("abbacabba"), length='unknown'); w
word: abbacabba
sage: w.to_integer_word()
word: 011020110

>>> from sage.all import *
>>> from itertools import count
>>> w = Word(count()); w
word: 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,...
>>> w.to_integer_word()
word: 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,...
>>> w = Word(iter("abbacabba"), length='finite'); w
word: abbacabba
>>> w.to_integer_word()
word: 011020110
>>> w = Word(iter("abbacabba"), length='unknown'); w
word: abbacabba
>>> w.to_integer_word()
word: 011020110