Abstract
Let sk(n) denote the sum of the digits of the base k representation of n. Define the sequence (or word) tk,m=s k(n)(mod m)n≥0, which generalizes the well-known ThueMorse sequence t2,2. We give a much shorter proof of the main result in Allouche and Shallit (2000) [1], which says that tk,m has no overlaps (that is, contains no subword of the form axaxa, where x is any finite word and a is a single symbol), using techniques from Cusick and Stǎnicǎ (2009) [2]. We also give different proofs of some other results from Allouche and Shallit (2000) [1] and one result from Morton and Mourant (1991) [3], using the same techniques.
| Original language | English |
|---|---|
| Pages (from-to) | 4738-4741 |
| Number of pages | 4 |
| Journal | Theoretical Computer Science |
| Volume | 412 |
| Issue number | 35 |
| DOIs | |
| State | Published - Aug 12 2011 |
Keywords
- Overlap
- Palindrome
- Sum of digits
- ThueMorse
Fingerprint
Dive into the research topics of 'Sum of digits sequences modulo m'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver