\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.1in} \setlength{\textheight}{8.4in} \newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}} \def\modd#1 #2{#1\ \mbox{\rm (mod}\ #2\mbox{\rm )}} \newcommand{\length}{\ensuremath{\mathrm{length}\,}} \usepackage{enumerate} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\LARGE\bf Sums of Digits and the Distribution of\\ \vskip .12in Generalized Thue-Morse Sequences } \vskip 1cm \Large Hancong Zhao and Dong Zhang\\ Peking University\\ Beijing 100871\\ P. R. China\\ \href{mailto:1401210046@pku.edu.cn}{\tt 1401210046@pku.edu.cn} \\ \href{mailto:dongzhang@pku.edu.cn}{\tt dongzhang@pku.edu.cn} \\ \end{center} \vskip .2 in \begin{abstract} In this paper we study the distribution of the infinite word $\mathrm{t}_{q,n}:=(s_q(k)\bmod n)_{k=0}^{\infty}$, which we call the generalized Thue-Morse sequence. Here $s_q(k)$ is the digit sum of $k$ in base $q$. We give an explicit formulation of the exact minimal value of $M$ such that every $M$ consecutive terms in $t_{q,n}$ cover the residue system of $n$, i.e., $\{0,1,\ldots,n-1\}$. Also, we prove some stronger related results. \end{abstract} \section{Introduction and main results} For $k\in\mathbb{N}$ and $q\in\{2,3,\ldots\}$, let $s_{q}(k)$ denote the sum of the digits of $k$ when expressed in base $q$. By convention, we use $k=(k_1^{d_1}k_2^{d_2}\cdots k_l^{d_l})_q$ to denote $$k=(\mathop {\underbrace{k_1k_1\cdots k_1}}\limits_{d_1}\mathop {\underbrace{k_2k_2\cdots k_2}}\limits_{d_2}\cdots\mathop {\underbrace{k_lk_l\cdots k_l}}\limits_{d_l})_q,$$ where we first have $d_{1}$ $k_{1}$s followed by $d_{2}$ $k_{2}$s, and so on up until $d_{l}$ $k_{l}$s, and omit every $d_{i}=1$. For example, the binary expansion of $6$ is $110$, so $6=(1^20)_2$ and $s_{2}(6)=1+1+0=2$. The sum of digits is an interesting object in number theory. In recent years, there have been some new results about the distribution of the digit sum sequence $(s_q(k))_{k=1}^{\infty}$. Morgenbesser, Shallit, and Stoll \cite{MSS2011} considered the classical Thue-Morse sequence $$(s_2(k)\bmod 2)_{k=1}^{\infty}.$$ They proved that the least number $k$ satisfying $s_2(d\cdot k)\equiv \modd{1} {2}$ is at most $d+4$, for every fixed positive integer $d$. For the general infinite word $\mathrm{t}_{q,n}:=(s_q(k)\bmod n)_{k=0}^{\infty}$, Allouche and Shallit \cite{AS2000} showed that the sequence $\mathrm{t}_{q,n}$ over the alphabet $\{0,1,\ldots,n-1\}$ is overlap-free if and only if $n\ge q$. In this paper we study the distribution of the generalized Thue-Morse sequence $\mathrm{t}_{q,n}$. We give the exact minimal positive integer $M_{q,n}$ (see Definition \ref{definition:Mqn}) such that every $M_{q,n}$ consecutive terms in $\mathrm{t}_{q,n}$ contain $j$ for every $j\in \{0,1,\ldots,n-1\}$. First we give some basic examples to help readers understand. \begin{example}[$M_{10,7}=13$]\rm \label{ex:7.10} Every $13$ consecutive positive integers have an element whose digit sum is divisible by $7$. But it is false for $12$ consecutive positive integers because the sums of digits of the numbers $994,995,\ldots,999$, $1000,1001,\ldots,1005$, are all not divisible by $7$. \end{example} \begin{example}[$M_{10,11}=39$]\rm \label{ex:11.10} Every $39$ consecutive positive integers have an element whose digit sum is divisible by $11$, but it is false for $38$ consecutive positive integers. In fact, it is easy to check that the sums of digits of the numbers $999981,999982,\ldots, 999999,1000000,1000001$, $\ldots,1000018$, are all not divisible by $11$. \end{example} The general results are given in Corollary \ref{cor:10}. Next, we introduce the positive integers $M_{q,n}$, where $n\in\mathbb{Z}^+$ and $q\in\{2,3,\ldots\}$. \begin{definition}\label{definition:Mqn} Let $q,n\in \mathbb{Z}^+$ with $q\ge 2$ and $n=k\cdot(q-1)+l$, where $l\in\{0,1,\ldots,q-2\}$ and $k\in \mathbb{N}$. For convenience, let \begin{equation}\label{eq:r} r=\begin{cases}\gcd(q-1,l)\cdot\left\lfloor\frac{l-1}{\gcd(q-1,l)}\right\rfloor,&\text{ if }1\le l\le q-2;\\0,&\text{ if }l=0.\end{cases} \end{equation} Now the number $M_{q,n}$ is defined to be $\left(l+r+1\right)\cdot q^k-1$, or equivalently $M_{q,n}=((l+r)(q-1)^k)_q$. \end{definition} Theorem \ref{them:main} and Theorem \ref{them:main2} are the main results of this paper. \begin{theorem}\label{them:main} The number $M_{q,n}$ is the least value of $M$, where every $M$ consecutive terms in $\mathrm{t}_{q,n}$ contain $0$. In other words, every $M_{q,n}$ consecutive positive numbers contain a number whose digit sum is divisible by $n$. And there exists a sequence of $M_{q,n}-1$ consecutive positive numbers such that it contains no integer whose digit sum is divisible by $n$. The least value of the first term of such sequence is \begin{equation}\label{eq:leastexample} \begin{cases}(1)_q,&\text{ if }\;\;l-1<\gcd(q-1,l);\\ ((q-1)^x(q-1-r)0^{k-1}1)_q,&\text{ if }\;\;l-1\ge \gcd(q-1,l), \end{cases} \end{equation} where $r$ is given in Eq.~\eqref{eq:r}, and $x$ is the minimal nonnegative integer solution of the congruence equation \begin{equation}\label{eq:congruence} (q-1)\cdot(x+1)-r\equiv0\pmod{(q-1)\cdot k+l}. \end{equation} \end{theorem} Theorem \ref{them:main2} is a strengthened form of Theorem \ref{them:main}. \begin{theorem}\label{them:main2} For every $j\in\{0,1,\ldots,n-1\}$, the minimum value of $M$, where every $M$ consecutive terms in $\mathrm{t}_{q,n}$ contain $j$, is also equal to $M_{q,n}$. In other words, every $M_{q,n}$ consecutive positive integers contain an integer $d$ with $s_q(d) \equiv \modd{j} {n}$. And there exists a sequence of $M_{q,n}-1$ consecutive positive integers containing no integer $d$ with $s_q(d) \equiv \modd{j} {n}$. The first term of such sequence can be chosen as $({1}^j0(q-1)^x(q-1-r)0^{k-1}1)_q$, where $x$ is a nonnegative integer solution of the congruence equation $(q-1)\cdot(x+1)-r\equiv \modd{0} {n}$. \end{theorem} \begin{remark} The facts below are true about $M_{q,n}$. \begin{enumerate}[1.] \item For the following set of sequences $\mathbb{A}_{q}(n)=\{(m+i)_{i=0}^k | m,\ldots,m+k\text{ are not divisible by }n,\text{ where } m,k\in \mathbb{Z}^+\},$ we have $\max\limits_{S\in\mathbb{A}_q(n)} \length(S)=M_{q,n}-1$. Here, $\length(S)$ represents the number of terms in sequence $S$. \item $M_{q,n}$ is the least value of $M$, where every $M$ consecutive terms in $\mathrm{t}_{q,n}$ cover the residue system of $n$, i.e., $\{0,1,\ldots,n-1\}$. \end{enumerate} \end{remark} \section{Proofs} In this section, we prove our main results. Before that, some lemmas as follows are needed. \begin{lemma}\label{lem:tongyu} For positive integers $a,b$ and $m$, the equation $ax\equiv \modd{b} {m}$ has a positive integer solutions if and only if $\gcd(a,m)|b$. \end{lemma} \begin{lemma}\label{lem:shushu} For fixed $h\in\{0,\ldots,{q-2}\}$ and $t\in\mathbb{N}$, the following statements are true. \begin{enumerate}[(1)] \item Consider a sequence of consecutive integers starting with zero. If no integer in this sequence has digit sum over $s:=(q-1)\cdot t+h$, then the length of the sequence is not longer than $((h+1)(q-1)^t)_q$ that has sum of digits $s+1$. \item Consider a sequence of consecutive nonnegative integers ending with $((q-1)^k)_q$. If every integer in this sequence has digit sum at least ${(q-1)}\cdot k-s+1$, then the length of the sequence is not longer than $(h(q-1)^t)_q$. \end{enumerate} \end{lemma} \begin{proof} (1) If $t\ge 1$, then $((h+1)(q-1)^t)_q-1=((h+1)(q-1)^{t-1}(q-2))_q$ has sum of digits $$(h+1)+(t-1)\cdot(q-1)+(q-2)=h+t\cdot(q-1)=s.$$ If $t=0$, then $((h+1)(q-1)^0)_q-1=h+1-1=h=s$ still has sum of digits $s$. Since the terms of the sequence are consecutive, the length of such sequence is not longer than $((h+1)(q-1)^t)_q-1+1=((h+1)(q-1)^t)_q$. (2) Let $((q-1)^k)_q$ minus $((q-1)^k)_q,\ldots,(1)_q,(0)_q$ respectively. Then the sequence in (2) starts with $0$, and no integer in this sequence has digit sum over $s-1$. Combining with $s-1=(q-1)\cdot t+h-1$ and the conclusion of (1), we can easily derive that the length of the sequence satisfying the condition is $(h(q-1)^t)_q$. \end{proof} Let $a_k(n)$ be the coefficient of $q^k$ of the representation of $n$ in base $q$ (i.e., $n=\sum_{k=0}^\infty a_k(n)q^k$, where $a_k(n)\in\{0,1,\ldots,q-1\}$) and let $v_q(n)=\max\{k\in \mathbb{N}:q^k|n\}$. We have the following result. \begin{lemma}\label{lem:carry} For every positive integer $A$, we have $s_{q}(A)=s_{q}(A+1)+{(q-1)}\cdot x-1$, where $x$ is the number of consecutive ${(q-1)}$ in the tail of $A$, or equivalently, $x=v_q(A+1)$. \end{lemma} Hereinafter, we use $[a,b]$ (resp., $[a,b)$, $(a,b)$ and $(a,b]$) to denote the set of integers in the interval $[a,b]$ (resp., $[a,b)$, $(a,b)$ and $(a,b]$), where $a$, $b$ are integers. \begin{lemma}\label{lem:cover}Below we make some relevant properties. \begin{enumerate}[(1)] \item For every integer $X$, $s_{q}(X)+1\geq s_{q}(X+1)$. \item Let $A,\ldots,B$ be consecutive positive integers satisfying $s_{q}(A)=\min\limits_{X\in[A,B]}s_{q}(X)$. Then $\{s_{q}(A),\ldots,s_{q}(B)\}=[s_{q}(A),\max\limits_{X\in[A,B]}s_{q}(X)]$. \item Let $A$, $A'$, $B$ and $B'$ be positive integers such that $B-A=B'-A'$, $s_{q}(A)=\min\limits_{X\in[A,B]}s_{q}(X)= s_{q}(A')=\min\limits_{X'\in[A',B']}s_{q}(X')$ and $s_{q}(A+C)\geq s_{q}(A'+C)$ for every $C\in[0,B-A]$. Then $\{s_{q}(A),\ldots,s_{q}(B)\}\supset\{s_{q}(A'),\ldots,s_{q}(B')\}$. \end{enumerate} \end{lemma} \begin{proof} (1) is easy to verify by Lemma \ref{lem:carry} and (3) can be deduced from (2). So it suffices to prove (2). Suppose the contrary, that there exists an integer $N\in(s_{q}(A),\max\limits_{X\in[A,B]}s_{q}(X))$ such that $s_{q}(X)\neq N$ for every $X\in[A,B]$. Let $C=\min\{D\in[A,B]\left|s_{q}(D)>N\right.\}$. Then by the definitions of $C$ and $N$, we have $s_{q}(C)>N$ and $s_{q}(C-1)N$, that is $s_{q}(C-1)\geq N$. This leads to a contradiction. \end{proof} \begin{lemma}\label{lem:all} Let $q,n\in \mathbb{Z}^+$ with $q\ge 2$ and $n=k\cdot(q-1)+l$, where $l\in\{0,1,\ldots,q-2\}$ and $k\in \mathbb{N}$. Every $(l(q-1)^k)_q$ consecutive terms of $\mathrm{t}_{q,n}$ with indexes in $[(A0^{k+1})_q,((A+1) 0^{k+1})_q)$ for some $A\in \mathbb{N}$, cover $\{0,1,\ldots,n-1\}$, where $A$ is always written in base $q$. \end{lemma} \begin{proof}Consider a sequence of $(l(q-1)^k)_q$ consecutive positive integers. We divide this proof into two cases. \medskip \noindent {\it Case 1:} $l\ge1$. In fact, the first $q^k=(10^k)_q$ terms of such sequence must contain a number $N$ satisfying $a_{i}(N)=0,i\in\{1,2,\ldots,k\}$ and $a_{k+1}(N)\in\{0,1,\ldots,q-l\}$. Therefore, the numbers $N, N+1, \ldots, N+(q-1), N+(1(q-1))_q, \ldots, N+((q-1)(q-1))_q, N+(1(q-1)(q-1))_q, \ldots, N+((q-1)(q-1)(q-1))_q, \ldots, N + ((q-1)^k)_q, N + (1(q-1)^k)_q, \ldots, N + ((l-1)(q-1)^k)_q$ all belong to such sequence, and they all belong to the interval $[(A0^{k+1})_q,((A+1) 0^{k+1})_q)$ as well. Their digit sums are respectively $s_{q}(N), s_{q}(N)+1, \ldots, s_{q}(N)+(q-1), s_{q}(N)+q, \ldots, s_{q}(N)+k\cdot(q-1), \ldots, s_{q}(N) + k\cdot(q-1)+l-1$, which cover all the residue classes modulo $k\cdot(q-1)+l$. \medskip \noindent{\it Case 2:} $l=0$. If the $((q-1)^k)_q$ consecutive positive integers lie in $[(Ab0^k)_q,(A b(q-1)^k)_q]$ for some $b\in \{0,1,\ldots,q-1\}$, then they must be $(Ab0^k)_q,(Ab0^{k-1}1)_q,\ldots,(Ab(q-1)^{k-1}(q-2))_q$ or $(Ab0^{k-1}1)_q,(Ab 0^{k-1}2)_q,\ldots,(Ab(q-1)^k)_q$, and their digit sums are $s(A)+b,s(A)+b+1,\ldots,s(A)+b+k\cdot(q-1)-1$ or $s(A)+b+1,s(A)+b+2,\ldots,s(A)+b+k\cdot(q-1)$, which cover the residue classes modulo $k\cdot(q-1)$. If the $((q-1)^k)_q$ consecutive positive integers are not in $[(Ab0^k)_q,(A b(q-1)^k)_q]$ for every $b\in\{0,1,\ldots,q-1\}$, then there exists an integer $b\in[0,q-2]$ such that $(Ab(q-1)^k)_q$ and $(A (b+1)0^k)_q$ are contained in these consecutive positive integers. Hence, there exists an integer $X$ with the form of $k$ digits\footnote{In fact, this means that $X$ should be taken from $\{({0}^{k-1}1)_q,(0^{k-1}2)_q,\ldots,((q-1)^k)_q\}$.} such that these consecutive positive integers can be written as $(AbX)_q,\ldots,(Ab(q-1)^k)_q,(A(b+1)0^k)_q,\ldots,(A(b+1)(X-2))_q$. Note that $s(A(b+1)Y)\ge s(Ab(Y+1))$ for every $Y$ with the form of $k$ digits. Thus, by Lemma \ref{lem:cover} (3) it is easy to verify that the digit sums of $(A(b+1)0^k)_q,\ldots,(A(b+1)(X-2))_q$ cover the digit sums of $(Ab0^{k-1}1)_q,\ldots,(Ab(X-1))_q$. Therefore, the digit sums of $(AbX)_q,\ldots,(Ab(q-1)^k)_q,(A(b+1)0^k)_q,\ldots,(A(b+1)(X-2))_q$ cover the digit sums of $(Ab0^{k-1}1)_q,(Ab0^{k-1}2)_q,\ldots,(Ab(q-1)^k)_q$, and consequently they cover the residue classes modulo $k\cdot(q-1)$. \end{proof} We are now ready to prove our main results. \begin{proof}[Proof of Theorem \ref{them:main}] We divide our proof into three steps. \medskip \noindent \textbf{Step 1}. In this step we prove every $M_{q,n}$ consecutive positive integers contain a number whose digit sum is divisible by $n$. Suppose the contrary, that there exists a sequence possessing $M_{q,n}$ consecutive positive integers which contains no number whose digit sum is divisible by $n$. By Lemma \ref{lem:all} and the fact that $(l(q-1)^k)_q\le M_{q,n}$ from the definition of $M_{q,n}$, the sequence is not contained in $[(A0^{k+1})_q,((A+1) 0^{k+1})_q)$ for every $A\in \mathbb{N}$. Furthermore, it is obvious that there exists an $A\in \mathbb{N}$ such that the sequence can be written in two parts \begin{equation}\label{eq:two-parts} \mathop {\underbrace{(As_1\cdots s_{k+1})_q,\ldots,(A(q-1)^{k+1})_q}}\limits_{\text{the first part}},\mathop {\underbrace{((A+1) 0^{k+1})_q,\ldots,((A+1)e_1\cdots e_{k+1})_q}}\limits_{\text{the second part}} \end{equation} where $s_i,e_i\in\{0,1,\ldots,q-1\}$ satisfy $$(A(q-1)^{k+1})_q-(As_1\cdots s_{k+1})_q< (l(q-1)^k)_q-1,$$ $$((A+1)e_1\cdots e_{k+1})_q-((A+1)0^{k+1})_q< (l(q-1)^k)_q-1$$ and $$((A+1)e_1\cdots e_{k+1})_q-(As_1\cdots s_{k+1})_q=M_{q,n}-1.$$ Notice that $$s_{q}((A(q-1)^{k+1})_q)=s_{q}(A)+{(q-1)}\cdot (k+1)$$ and $$s_{q}(((A+1)0^{k+1})_q)=s_{q}(A+1).$$ Suppose \begin{equation}\label{eq:modalpha} s_{q}(A)+{(q-1)}\cdot(k+1)\equiv\alpha\pmod{(q-1)\cdot k+l} \end{equation} and \begin{equation}\label{eq:modbeta} s_q(A+1)\equiv\beta\pmod{(q-1)\cdot k+l}, \end{equation} where $\alpha,\beta\in \{0,1,2,\ldots,{(q-1)}\cdot k+l-1\}$. Since every number $F$ in the sequence shown in \eqref{eq:two-parts} satisfies $s_q(F)\not\equiv\modd{0} {n}$, we indeed have \begin{equation}\label{eq:alphabeta} \alpha,\beta\in \{1,2,\ldots,{(q-1)}\cdot k+l-1\}. \end{equation} Then the digit sums of the second part of the sequence shown in \eqref{eq:two-parts} are contained in the following $n-\beta$ numbers: \begin{equation}\label{eq:right} s_q(A+1),\ldots,s_q(A+1)+{(q-1)}\cdot k+l-1-\beta. \end{equation} The digit sums of the first part of the sequence shown in \eqref{eq:two-parts} are contained in the following $\alpha$ numbers: \begin{equation}\label{eq:left} s_q(A)+{(q-1)}\cdot (k+1)-\alpha+1,\ldots,s_q(A)+{(q-1)}\cdot(k+1). \end{equation} By Lemma \ref{lem:carry}, we have $s_q(A)=s_q(A+1)+{(q-1)}\cdot x-1$, where $x$ is the number of consecutive ${(q-1)}$ in the tail of $A$, i.e., $x:=v_q(A+1)$. Hence, we deduce from \eqref{eq:modalpha} that $$s_q(A+1)+{(q-1)}\cdot x-1+{(q-1)}\cdot (k+1)\equiv\alpha\pmod{(q-1)\cdot k+l}.$$ Combining with \eqref{eq:modbeta}, we have \begin{equation}\label{eq:mod} \beta-\alpha+{(q-1)}\cdot(x+k+1)-1\equiv0\pmod{(q-1)\cdot k+l}. \end{equation} According to Lemma \ref{lem:tongyu}, \eqref{eq:mod} has a positive integer solution if and only if $\gcd(q-1,(q-1)\cdot k+l)|\alpha+1-\beta$, namely \begin{equation}\label{eq:q-1} \gcd(q-1,l)|\alpha+1-\beta. \end{equation} A quick inspection of \eqref{eq:alphabeta} reveals $\alpha+1-\beta\le (q-1)\cdot k+l-1$. Note that $(q-1)\cdot k+r$ is the largest integer which is divisible by $\gcd(q-1,l)$ and not larger than $(q-1)\cdot k+l-1$. Thus, combining with \eqref{eq:alphabeta} and \eqref{eq:q-1}, it is easy to see that $\alpha+1-\beta$ is not larger than $(q-1)\cdot k+r$. Next, in order to get a contradiction, we will estimate the lengths of the two parts of the sequence shown in \eqref{eq:two-parts}. \begin{enumerate}[(I).] \item We will apply Lemma \ref{lem:shushu} (1) to the second part of the sequence. Combining with Lemma \ref{lem:all}, we know that the number of the consecutive integers behind $(A+1)0^{k+1}$ is less than $(l(q-1)^{k})_q$, and then these integers all have the form $((A+1)X)_q$, where $X$ possesses at most $k+1$ digits. Thus, from $s_q(((A+1)X)_q)=s_q(A+1)+s_q(X)$ and \eqref{eq:right} we know \begin{align} s_q(X)&=s_q(((A+1)X)_q)-s_q(A+1) \notag \\&\le s_q(A+1)+{(q-1)}\cdot k+l-1-\beta-s_q(A+1) \notag \\&={(q-1)}\cdot k+l-1-\beta \label{eq:I-sq-k} \\&:=(q-1)\cdot m+\beta_{1},\label{eq:I-sq-m} \end{align} where $m\leq k$ and $\beta_{1}\in\{0,1,\ldots,q-2\}$. Note that the least value of $s_q(X)$ is $0$. Therefore, by Lemma \ref{lem:shushu} (1), we can obtain that the length of the second part of the sequence is at most $((\beta_{1}+1)(q-1)^m)_q$. \item We will apply Lemma \ref{lem:shushu} (2) to the first part of the sequence. Combining with Lemma \ref{lem:all}, we know that the number of the consecutive integers before $(A(q-1)^{k+1})_q$ is less than $(l(q-1)^k)_q$, and then obtain these integers all have the form $(AY)_q$, where $Y$ possesses at most $k+1$ digits. Therefore, from $s_q((AY)_q)=s_q(A)+s_q(Y)$ and \eqref{eq:left}, we have \begin{align*} s_q(Y)&=s_q((AY)_q)-s_q(A) \\&\ge s_q(A)+{(q-1)}\cdot(k+1)-\alpha+1-s_q(A) \\&={(q-1)}\cdot(k+1)-\alpha+1. \end{align*} Let $\alpha=(q-1)\cdot t+h$, where $t\leq k$ and $h\in\{0,1,\ldots,q-2\}$. Since $Y$ ends up with $(q-1)^{k+1}$, by Lemma \ref{lem:shushu} (2), the length of the first part of the sequence must be at most $h(q-1)^t$. \end{enumerate} Summing up the above, we obtain the length of this sequence is at most \begin{equation*}\label{eq:length} ((\beta_{1}+1)(q-1)^m)_q+(h(q-1)^t)_q. \end{equation*} Since $(h(q-1)^t)_q< ((q-1)^k)_q$ for $t\le k-1$, we should let $t=k$ to make $((\beta_1+1)(q-1)^m)_q+(h(q-1)^t)_q$ as large as possible. And then, we obtain from (II) that $h=\alpha-(q-1)\cdot k$. Since $((\beta_1+1)(q-1)^m)_q\le ((q-1)^{k-1})_q<((q-1)^k)_q$ for $m\le k-2$, we should take $m\in\{k-1,k\}$ to make $((\beta_1+1)(q-1)^m)_q+(h(q-1)^t)_q$ as large as possible. If $l=0$, \eqref{eq:I-sq-k} and \eqref{eq:I-sq-m} imply $m\le k-1$ and thus we should let $m=k-1$. Then, we obtain from (I) that $q-1-1-\beta=\beta_1\le q-2$. Hence, $((\beta_1+1)(q-1)^m)_q\le ((q-1)^k)_q$. To make $((\beta_1+1)(q-1)^m)_q+(h(q-1)^t)_q$ as large as possible, we should take $\beta_1=q-2$. And in this case, $\beta=l=0$. If $l\ge 1$, \eqref{eq:I-sq-k} and \eqref{eq:I-sq-m} imply $m\le k$ and thus we should let $m=k$. Then, we obtain from (I) that $l-1-\beta=\beta_1\ge 0$. Note that in both cases, we have \begin{align} ((\beta_{1}+1)(q-1)^m)_q+(h(q-1)^t)_q &=((l-\beta)(q-1)^k)_q+((\alpha-(q-1)\cdot k)(q-1)^k)_q\notag \\&=((l+\alpha+1-\beta-(q-1)\cdot k)(q-1)^k)_q-1 \notag \\&\le ((l+r)(q-1)^k)_q-1=M_{q,n}-1,\label{eq:(q-1)timesk+r} \end{align} which is a contradiction. The proof in Step 1 is completed. \medskip \noindent \textbf{Step 2}. In this step, we will prove there exists a sequence of $M_{q,n}-1$ consecutive positive numbers containing no integer whose digit sum is divisible by $n$. Note that in the case of $l-1<\gcd(q-1,l)$, we have $M_{q,n}=(l(q-1)^k)_q$ by Definition \ref{definition:Mqn}, and thus the numbers $1,2,\ldots,(l(q-1)^{k-1}(q-2))_q$ are $M_{q,n}-1$ consecutive positive integers containing no integer whose digit sum is divisible by $n=k\cdot (q-1)+l$. So we only need to explain the case of $l-1\ge\gcd(q-1,l)$ for detail. Now, we verify the following $M_{q,n}-1=((l+r)(q-1)^k)_q-1$ consecutive positive integers \begin{equation}\label{eq:example} \mathop {\underbrace{((q-1)^x(q-1-r)0^{k-1}1)_q, \ldots, ((q-1)^{x+1+k})_q}}\limits_{\text{the first part}}, \mathop {\underbrace{ (10^{x+1+k})_q, \ldots, (1 0^x (l-1)(q-1)^{k-1}(q-2))_q }}\limits_{\text{the second part}} \end{equation} contain no integer whose digit sum is divisible by $n$. The sums of digits of the integers in the first part shown in \eqref{eq:example} are contained in $(q-1)\cdot x+q-r, \ldots, (q-1)\cdot (x+1+k)$, which equal to $1,2,\ldots, (q-1)\cdot k+r$ modulo $n$ according to Eq.~(\ref{eq:congruence}). The sums of digits of the integers in the second part shown in \eqref{eq:example} are contained in $1,\ldots,(q-1)\cdot k+l-1$, which equal to $1,2,\ldots, (q-1)\cdot k+l-1$ modulo $n$ by Eq.~\eqref{eq:congruence}. \medskip \noindent \textbf{Step 3}. To complete our proof, it remains to show that \eqref{eq:example} is the smallest $M_{q,n}-1$ consecutive positive numbers containing no integer whose digit sum is divisible by $n$. According to Step 2, it suffices to consider the case of $l-1\ge\gcd(q-1,l)$. In this step, the length of the sequence is $M_{q,n}-1$. So in inequality \eqref{eq:(q-1)timesk+r}, $((\beta_1+1)(q-1)^m)_q+(h(q-1)^t)_q=M_{q,n}-1$, which means \begin{equation}\label{eq:turn-to-equality} \alpha+1-\beta=(q-1)\cdot k+r. \end{equation} Combining with \eqref{eq:mod}, we have \begin{equation}\label{eq:mod-simple} {(q-1)}\cdot(x+1)- r \equiv0\pmod{(q-1)\cdot k+l}. \end{equation} As the priori proof in Step 1, the smallest number possesses the form $(AY)_q$. By $x=v_q(A+1)$, the minimal possible value of $A$ is $((q-1)^x)_q$. Continuing the proof in Step 1, one can get the number of digits of $Y$ (followed by $A$) must be $k+1$. To make $(AY)_q$ as small as possible, we let $A=((q-1)^x)_q$. Equality \eqref{eq:turn-to-equality} implies that $\alpha=(q-1)\cdot k+r+\beta-1\ge (q-1)\cdot k+r$. So, we may assume that $\alpha=(q-1)\cdot k+r'$, where $r'\in\{0,1,\ldots,l-1\}$. Then we can simplify \eqref{eq:modalpha} further to \begin{equation}\label{eq:mod-simple2} s_{q}(A)+q-1-r'\equiv0 \pmod{(q-1)\cdot k+l}. \end{equation} Together with \eqref{eq:mod-simple}, \eqref{eq:mod-simple2} and $A=((q-1)^x)_q$, we immediately obtain $r'=r$. From (II) in Step 1, we can obtain that the length of the first part of the sequence is $r(q-1)^k$. Thus, the first term of such sequence is $$(A(q-1)^{k+1})_q-(r(q-1)^k)_q+1 =((q-1)^x(q-1)^{k+1})_q-(r(q-1)^k)_q+1=( (q-1)^x(q-1-r)0^{k-1}1)_q.$$ By Step 2 and the discussions above in Step 3, the first term $((q-1)^x(q-1-r)0^{k-1}1)_q$ is the smallest possible one. \end{proof} \begin{proof}[Proof of Theorem \ref{them:main2}] Suppose the contrary, that for some integer $j$, there exists a sequence of $M_{q,n}$ consecutive positive integers containing no integer $d$ with $s_q(d) \equiv \modd{j} {n}$. For simplicity, we use $m_1, m_2,\ldots, m_{M_{q,n}}$ to denote these consecutive integers. Let $c$ be the number of the digits of $m_{M_{q,n}}$, and let $b=\sum\limits_{k=1}^{n-j}q^{k+c}$. Then $s_q(m_i)+n-j=s_q(m_i+b)$, $i\in\{1,2,\ldots,M_{q,n}\}$. Note that $s_q(m_i) \neq \modd{j} {n}$ means $s_q(m_i+b) \neq \modd{0} {n}$. Therefore, the new sequence $\{m_k+b\}_{k=1}^{M_{q,n}}$ is consecutive, but it contains no integer $m_i+b$ with $s_q(m_i+b) \equiv \modd{0} {n}$, which is a contradiction with Theorem \ref{them:main}. \end{proof} \section{Further conclusions and open problems} From Theorem \ref{them:main}, it is easy to obtain the special results below. \begin{corollary}[Binary system case]\label{cor:2} $M_{2,n}=2^n-1$. \end{corollary} \begin{corollary}[Decimalism case]\label{cor:10} Let $n=9\cdot k+l$, $k \in \mathbb{N}$, and $l \in \{ 1,2,3,4,5,6,7,8,9\}$, and then we have $M_{10,n} = (M_{10,l} + 1) \cdot {10^k} - 1$. The details are presented in Table~\ref{table1}. \begin{table}[H] \begin{center} \begin{tabular}{||c||c|c|c|c||} \hline\hline $l$ & $M_{10,9k+l}$ & example on $k=0$ & example on $k \in {\mathbb{Z}^ + }$ \\ \hline\hline 1&$(19^k)_{10}$&$(1)_{10}$&$(1)_{10}$\\ \hline 2&$(39^k)_{10}$&$(9)_{10}$&$(9^{4k} 8 0^{k - 1} 1)_{10}$\\ \hline 3&$(39^k)_{10}$&$(1)_{10}$&$(1)_{10}$\\ \hline 4&$(79^k)_{10}$&$(997)_{10}$&$(9^{6k + 2} 60^{k - 1} 1)_{10}$\\ \hline 5&$(99^k)_{10}$&$(6)_{10}$&$(9^k 5 0^{k - 1} 1)_{10}$\\ \hline 6&$(99^k)_{10}$&$(7)_{10}$&$ (9^k 6 0^{k - 1} 1)_{10}$\\ \hline 7&$(139^k)_{10}$&$(994)_{10}$&$(9^{3k + 2} 3 0^{k - 1} 1)_{10}$\\ \hline 8&$(159^k)_{10}$&$(9999993)_{10}$&$(9^{7k + 6} 20^{k - 1} 1)_{10}$\\ \hline 9&$(99^k)_{10}$&$(1)_{10}$&$(1)_{10}$\\ \hline\hline \end{tabular} \end{center} \begin{center} \begin{minipage}{9cm } \caption{This table is a detailed explanation about Corollary \ref{cor:10}, in which we symbolically set $(19^0)_{10}= 1$, and the third and fourth columns of this table are the concrete realizations of Eq.~\eqref{eq:leastexample}.} \label{table1} \end{minipage}\end{center} \end{table} \end{corollary} Corollary \ref{cor:10} is a general form of Examples \ref{ex:7.10} and \ref{ex:11.10}. To illustrate Table~\ref{table1}, we show two examples: For $l=8$ and $k=0$, we obtain from Table~\ref{table1} that $M_{10,8}=15$ and the $14$ numbers, $9999993, 9999994, \ldots, 10000006$, are the smallest $14$ consecutive positive integers whose digit sums are all not divisible by $8$. For $l=6$ and $k=1$, Table~\ref{table1} shows that $M_{10,15}=99$ and the $98$ numbers, $961, 962, \ldots, 1058$, are the smallest $98$ consecutive positive integers whose digit sums are all not divisible by $15$. Finally, we give some open problems. \begin{enumerate}[1.] \item How to extend the method in this paper to prove results about $(s_q(a k) \bmod n)_{k=1}^\infty$ for given integers $q,n,a\ge 2$? \item How often do $M_{q,n}$ consecutive terms in $\mathrm{t}_{q,n}$ cover $\{0, 1,\ldots, n-1\}$? \end{enumerate} \begin{thebibliography}{1} \bibitem{MSS2011} J. F. Morgenbesser, J. Shallit and T. Stoll, Thue-Morse at multiples of an integer, {\sl J. Number Theory.} \textbf{131} (2011), 1498--1512. \bibitem{AS2000} J.-P. Allouche and J. Shallit, Sums of digits, overlaps, and palindromes, {\sl Discrete Math. Theor. Comput. Sci.} \textbf{4} (2000), 1--10. \end{thebibliography} \bigskip \hrule\bigskip \noindent 2010 \textit{Mathematics Subject Classification}: 11B99, 11Y55, 11N25, 11A63, 68R15. \noindent \emph{Keywords: } digit sum, Thue-Morse sequence. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A010060} and \seqnum{A141803}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received April 12 2016; revised version received July 24 2016; August 31 2016; January 7 2017. Published in {\it Journal of Integer Sequences}, January 7 2017. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document} .