Skip to Main content Skip to Navigation
Journal articles

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) \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.
Document type :
Journal articles
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download

https://hal.inria.fr/hal-00958941
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Thursday, March 13, 2014 - 4:49:23 PM
Last modification on : Wednesday, September 16, 2020 - 4:56:15 PM
Long-term archiving on: : Friday, June 13, 2014 - 12:02:21 PM

File

dm040101.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00958941, version 1

Collections

Citation

Jean-Paul Allouche, Jeffrey Shallit. Sums of Digits, Overlaps, and Palindromes. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2000, 4 (1), pp.1-10. ⟨hal-00958941⟩

Share

Metrics

Record views

198

Files downloads

1039