HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 Connect in order to contact the contributor
Submitted on : Thursday, March 13, 2014 - 4:49:23 PM
Last modification on : Thursday, July 8, 2021 - 3:47:49 AM
Long-term archiving on: : Friday, June 13, 2014 - 12:02:21 PM

File

dm040101.pdf
Files produced by the author(s)

Identifiers

Citation

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

Share

Metrics

Record views

91

Files downloads

776