Discrete Mathematics & Theoretical Computer Science
Volume 4 n° 1 (2000), pp. 1-10
| author: | Jean-Paul Allouche and Jeffrey Shallit |
|---|---|
| title: | Sums of Digits, Overlaps, and Palindromes |
| keywords: | sum of digits, overlap-free sequence, palindrome |
| abstract: | Let s_k(n) denote the sum of the digits in the base-k representation of n. In a celebrated paper, Thue showed that the infinite word s_2(n) mod 2)_{n>=0} is overlap-free, i.e., contains no subword of the form axaxa where x is any finite word and a is a single symbol. Let k,m be integers with k>2, m>=1. In this paper, generalizing Thue's result, we prove that the infinite word t_{k,m} := (s_k(n) mod m)_{n>=0} is overlap-free if and only if m>=k. We also prove that t_{k,m} contains arbitrarily long squares (i.e., subwords of the form xx where x is nonempty), and contains arbitrarily long palindromes if and only if m<= 2. |
| reference: | Jean-Paul Allouche and Jeffrey Shallit (2000), Sums of Digits, Overlaps, and Palindromes, Discrete Mathematics and Theoretical Computer Science 4, pp. 1-10 |
| ps.gz-source: | dm040101.ps.gz (40 K) |
| ps-source: | dm040101.ps (107 K) |
| pdf-source: | dm040101.pdf (112 K) |
The first source gives you the `gzipped' PostScript, the second the plain PostScript and the third the format for the Adobe accrobat reader. Depending on the installation of your web browser, at least one of these should (after some amount of time) pop up a window for you that shows the full article. If this is not the case, you should contact your system administrator to install your browser correctly.
Automatically produced on Thu Dec 7 13:49:08 CET 2000 by jc