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 Palindromes

Authors: Jean-Paul Allouche ORCID-iD1; Jeffrey Shallit ORCID-iD2

  • 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

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo DOI 10.1090/s0002-9947-1921-1501161-8
  • 10.1090/s0002-9947-1921-1501161-8
  • 10.1090/s0002-9947-1921-1501161-8
Recurrent geodesics on a surface of negative curvature

Consultation statistics

This page has been seen 258 times.
This article's PDF has been downloaded 225 times.