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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2000, 4 (1), pp.1-10
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00958941
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : jeudi 13 mars 2014 - 16:49:23
Dernière modification le : jeudi 11 janvier 2018 - 06:20:11
Document(s) archivé(s) le : vendredi 13 juin 2014 - 12:02:21

Fichier

dm040101.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00958941, version 1

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〉

Partager

Métriques

Consultations de la notice

73

Téléchargements de fichiers

131