Sums of Digits, Overlaps, and Palindromes

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.