\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$. However, according to (1), $s_{q}(C-1)+1\geq s_{q}(C)>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}

                                                                                



.
