Allouche, Jean-Paul and Shallit, Jeffrey - Sums of Digits, Overlaps, and Palindromes

dmtcs:282 - Discrete Mathematics & Theoretical Computer Science, January 1, 2000, Vol. 4 no. 1
Sums of Digits, Overlaps, and Palindromes

Authors: Allouche, Jean-Paul and Shallit, Jeffrey

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) \bmod 2)_n≥ 0 is \emphoverlap-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) \bmod 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.

Source : oai:HAL:hal-00958941v1
Volume: Vol. 4 no. 1
Published on: January 1, 2000
Submitted on: March 26, 2015
Keywords: sum of digits,overlap-free sequence,palindrome,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]


Browsing statistics

This page has been seen 66 times.
This article's PDF has been downloaded 36 times.