Discrete Mathematics & Theoretical Computer Science, Vol 4, No 1 (2000)

Font Size:  Small  Medium  Large

Sums of Digits, Overlaps, and Palindromes

Jean-Paul Allouche, Jeffrey Shallit


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