Jean-Paul Allouche ; Jeffrey Shallit - 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 PalindromesArticle

Authors: Jean-Paul Allouche ORCID1; Jeffrey Shallit ORCID2

  • 1 Laboratoire de Recherche en Informatique
  • 2 Department of Computer Science [Waterloo ]

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.

Volume: Vol. 4 no. 1
Published on: January 1, 2000
Imported on: March 26, 2015
Keywords: sum of digits,overlap-free sequence,palindrome,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
    Source : OpenAIRE Graph
  • Funder: Natural Sciences and Engineering Research Council of Canada

2 Documents citing this article

Consultation statistics

This page has been seen 344 times.
This article's PDF has been downloaded 305 times.