### Sums of Digits, Overlaps, and Palindromes

*Jean-Paul Allouche, Jeffrey Shallit*

#### Abstract

Let sk(n) denote the sum of the digits in the base-k representation of n. In a celebrated paper, Thue showed that the infinite word (s2(n) &bmod; 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 tk,m := (sk(n) &bmod; m)n≥0 is overlap-free if and only if m≥k. We also prove that tk,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.Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page