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.

Source : oai:HAL:hal-00958941v1

Volume: Vol. 4 no. 1

Published on: January 1, 2000

Submitted on: March 26, 2015

Keywords: sum of digits,overlap-free sequence,palindrome,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

This page has been seen 66 times.

This article's PDF has been downloaded 36 times.