Sums of Digits and the Distribution of Generalized Thue-Morse Sequences

Hancong Zhao and Dong Zhang Peking University Beijing 100871 P. R. China

            1401210046@pku.edu.cn
             dongzhang@pku.edu.cn

Abstract

In this paper we study the distribution of the infinite word t_{q,n} := (s_{q}(k) mod n)_{k=0}^{∞}, 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, …, n − 1}. Also, we prove some stronger related results.

1 Introduction and main results

For k ∈ ℕ and q ∈ {2, 3, …}, 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}} ⋯ k_{l}^{d_{l}})_{q} to denote

k = (\underbrace{k_{1}k_{1} ⋯ k_{1}}_{d_{1}} \underbrace{k_{2}k_{2} ⋯ k_{2}}_{d_{2}} ⋯ \underbrace{k_{l}k_{l} ⋯ k_{l}}_{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^{2}0)_{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}^{∞}. Morgenbesser, Shallit, and Stoll [1] considered the classical Thue-Morse sequence

(s_{2}(k) mod 2)_{k=1}^{∞}.

They proved that the least number k satisfying s_{2}(d · k) ≡ 1 (mod 2) is at most d + 4, for every fixed positive integer d. For the general infinite word t_{q,n} := (s_{q}(k) mod n)_{k=0}^{∞}, Allouche and Shallit [2] showed that the sequence t_{q,n} over the alphabet {0, 1, …, n − 1} is overlap-free if and only if n ≥ q.

In this paper we study the distribution of the generalized Thue-Morse sequence t_{q,n}. We give the exact minimal positive integer M_{q,n} (see Definition 3) such that every M_{q,n} consecutive terms in t_{q,n} contain j for every j ∈ {0, 1, …, n − 1}. First we give some basic examples to help readers understand.

Example 1 (M_{10,7} = 13). 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, …, 999, 1000, 1001, …, 1005, are all not divisible by 7.

Example 2 (M_{10,11} = 39). 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, …, 999999, 1000000, 1000001, …, 1000018, are all not divisible by 11.

The general results are given in Corollary 13.

Next, we introduce the positive integers M_{q,n}, where n ∈ ℤ^{+} and q ∈ {2, 3, …}.

Definition 3. Let q, n ∈ ℤ^{+} with q ≥ 2 and n = k · (q − 1) + l, where l ∈ {0, 1, …, q − 2} and k ∈ ℕ. For convenience, let

r = \begin{cases}gcd(q − 1, l) · ⌊\frac{l−1}{gcd(q−1,l)}⌋ , & if 1 ≤ l ≤ q − 2; \\ 0, & if l = 0. \end{cases}  (1)

Now the number M_{q,n} is defined to be (l + r + 1) · q^{k} − 1, or equivalently M_{q,n} = ((l + r)(q − 1)^{k})_{q}.

Theorem 4 and Theorem 5 are the main results of this paper.

Theorem 4. The number M_{q,n} is the least value of M, where every M consecutive terms in 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{cases}(1)_{q}, & if l − 1 < gcd(q − 1, l); \\ ((q − 1)^{x}(q − 1 − r)0^{k−1}1)_{q}, & if l − 1 ≥ gcd(q − 1, l), \end{cases}  (2)

where r is given in Eq. (1), and x is the minimal nonnegative integer solution of the congruence equation

(q − 1) · (x + 1) − r ≡ 0 (mod (q − 1) · k + l).  (3)

Theorem 5 is a strengthened form of Theorem 4.

Theorem 5. For every j ∈ {0, 1, …, n − 1}, the minimum value of M, where every M consecutive terms in 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) ≡ j (mod n). And there exists a sequence of M_{q,n} − 1 consecutive positive integers containing no integer d with s_{q}(d) ≡ j (mod n). The first term of such sequence can be chosen as (1^{j}0(q − 1)^{x}(q − 1 − r)0^{k−1}1)_{q}, where x is a nonnegative integer solution of the congruence equation (q − 1) · (x + 1) − r ≡ 0 (mod n).

Remark 6. The facts below are true about M_{q,n}.

1. For the following set of sequences

𝔸_{q}(n) = {(m + i)_{i=0}^{k}|m, …, m + k are not divisible by n, where m, k ∈ ℤ^{+}},

we have max_{S∈𝔸_{q}(n)} length (S) = M_{q,n} − 1. Here, length (S) represents the number of terms in

sequence S.

2. M_{q,n} is the least value of M, where every M consecutive terms in t_{q,n} cover the residue system of n, i.e., {0, 1, …, n − 1}.

2 Proofs

In this section, we prove our main results. Before that, some lemmas as follows are needed.

Lemma 7. For positive integers a, b and m, the equation ax ≡ b (mod m) has a positive integer solutions if and only if gcd(a, m)|b.

Lemma 8. For fixed h ∈ {0, …, q − 2} and t ∈ ℕ, the following statements are true.

(1) Consider a sequence of consecutive integers starting with zero. If no integer in this sequence has digit sum over s := (q − 1) · 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.

(2) 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) · k − s + 1, then the length of the sequence is not longer than (h(q − 1)^{t})_{q}.

Proof. (1) If t ≥ 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) · (q − 1) + (q − 2) = h + t · (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}, …, (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) · 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}.

Let a_{k}(n) be the coefficient of q^{k} of the representation of n in base q (i.e., n = ∑_{k=0}^{∞} a_{k}(n)q^{k}, where a_{k}(n) ∈ {0, 1, …, q − 1}) and let v_{q}(n) = max{k ∈ ℕ : q^{k}|n}. We have the following result.

Lemma 9. For every positive integer A, we have s_{q}(A) = s_{q}(A + 1) + (q − 1) · x − 1, where x is the number of consecutive (q − 1) in the tail of A, or equivalently, x = v_{q}(A + 1).

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.

Lemma 10. Below we make some relevant properties.

(1) For every integer X, s_{q}(X) + 1 ≥ s_{q}(X + 1).

(2) Let A, …, B be consecutive positive integers satisfying s_{q}(A) = min_{X∈[A,B]} s_{q}(X). Then

{s_{q}(A), …, s_{q}(B)} = [s_{q}(A), max_{X∈[A,B]} s_{q}(X)].

(3) Let A, A′, B and B′ be positive integers such that B−A = B′−A′, s_{q}(A) = min_{X∈[A,B]} s_{q}(X) =

s_{q}(A′) = min_{X′∈[A′,B′]} s_{q}(X′) and s_{q}(A + C) ≥ s_{q}(A′ + C) for every C ∈ [0, B − A]. Then

{s_{q}(A), …, s_{q}(B)} ⊃ {s_{q}(A′), …, s_{q}(B′)}.

Proof. (1) is easy to verify by Lemma 9 and (3) can be deduced from (2). So it suffices to prove (2).

Suppose the contrary, that there exists an integer N ∈ (s_{q}(A), max_{X∈[A,B]} s_{q}(X)) such that

s_{q}(X) ≠ N for every X ∈ [A, B].

Let C = min{D ∈ [A, B] |s_{q}(D) > N }. 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 ≥ s_{q}(C) > N, that is s_{q}(C − 1) ≥ N. This leads to a contradiction.

Lemma 11. Let q, n ∈ ℤ^{+} with q ≥ 2 and n = k · (q − 1) + l, where l ∈ {0, 1, …, q − 2} and k ∈ ℕ. Every (l(q − 1)^{k})_{q} consecutive terms of t_{q,n} with indexes in [(A0^{k+1})_{q}, ((A + 1)0^{k+1})_{q}) for some A ∈ ℕ, cover {0, 1, …, n − 1}, where A is always written in base q. Proof. Consider a sequence of (l(q −1)^{k})_{q} consecutive positive integers. We divide this proof into two cases. Case 1: l ≥ 1. In fact, the first q^{k} = (10^{k})_{q} terms of such sequence must contain a number N satisfying a_{i}(N) = 0, i ∈ {1, 2, …, k} and a_{k+1}(N) ∈ {0, 1, …, q−l}. Therefore, the numbers N, N +1, …, N +(q−1), N +(1(q−1))_{q}, …, N +((q−1)(q−1))_{q}, N +(1(q−1)(q−1))_{q}, …, N + ((q−1)(q−1)(q−1))_{q}, …, N +((q−1)^{k})_{q}, N +(1(q−1)^{k})_{q}, …, 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, …, s_{q}(N) + (q − 1), s_{q}(N) + q, …, s_{q}(N) + k · (q −1), …, s_{q}(N)+k ·(q −1)+l −1, which cover all the residue classes modulo k ·(q −1)+l. Case 2: l = 0. If the ((q −1)^{k})_{q} consecutive positive integers lie in [(Ab0^{k})_{q}, (Ab(q −1)^{k})_{q}] for some b ∈ {0, 1, …, q − 1}, then they must be (Ab0^{k})_{q}, (Ab0^{k−1}1)_{q}, …, (Ab(q − 1)^{k−1}(q − 2))_{q} or (Ab0^{k−1}1)_{q}, (Ab0^{k−1}2)_{q}, …, (Ab(q − 1)^{k})_{q}, and their digit sums are s(A) + b, s(A) + b + 1, …, s(A) + b + k · (q − 1) − 1 or s(A) + b + 1, s(A) + b + 2, …, s(A) + b + k · (q − 1), which cover the residue classes modulo k · (q − 1).

If the ((q − 1)^{k})_{q} consecutive positive integers are not in [(Ab0^{k})_{q}, (Ab(q − 1)^{k})_{q}] for every b ∈ {0, 1, …, q − 1}, then there exists an integer b ∈ [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^{1} such that these consecutive positive integers can be written as (AbX)_{q}, …, (Ab(q − 1)^{k})_{q}, (A(b + 1)0^{k})_{q}, …, (A(b + 1)(X − 2))_{q}. Note that s(A(b+1)Y) ≥ s(Ab(Y +1)) for every Y with the form of k digits. Thus, by Lemma 10 (3) it is easy to verify that the digit sums of (A(b+1)0^{k})_{q}, …, (A(b+1)(X−2))_{q} cover the digit sums of (Ab0^{k−1}1)_{q}, …, (Ab(X − 1))_{q}. Therefore, the digit sums of (AbX)_{q}, …, (Ab(q − 1)^{k})_{q}, (A(b + 1)0^{k})_{q}, …, (A(b+1)(X−2))_{q} cover the digit sums of (Ab0^{k−1}1)_{q}, (Ab0^{k−1}2)_{q}, …, (Ab(q−1)^{k})_{q}, and consequently they cover the residue classes modulo k · (q − 1).

We are now ready to prove our main results.

Proof of Theorem 4. We divide our proof into three steps. 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 11 and the fact that (l(q − 1)^{k})_{q} ≤ 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 ∈ ℕ. Furthermore, it is obvious that there exists an A ∈ ℕ such that the sequence can be written in two parts

\underbrace{(As_{1} ⋯ s_{k+1})_{q}, …, (A(q − 1)^{k+1})_{q}}_{the first part}, \underbrace{((A + 1)0^{k+1})_{q}, …, ((A + 1)e_{1} ⋯ e_{k+1})_{q}}_{the second part}  (4)

1In fact, this means that X should be taken from {(0^{k−1}1)_{q}, (0^{k−1}2)_{q}, …, ((q − 1)^{k})_{q}}.

where s_{i}, e_{i} ∈ {0, 1, …, q − 1} satisfy

(A(q − 1)^{k+1})_{q} − (As_{1} ⋯ s_{k+1})_{q} < (l(q − 1)^{k})_{q} − 1,
((A + 1)e_{1} ⋯ e_{k+1})_{q} − ((A + 1)0^{k+1})_{q} < (l(q − 1)^{k})_{q} − 1

and

((A + 1)e_{1} ⋯ e_{k+1})_{q} − (As_{1} ⋯ s_{k+1})_{q} = M_{q,n} − 1.

Notice that

s_{q}((A(q − 1)^{k+1})_{q}) = s_{q}(A) + (q − 1) · (k + 1)

and

s_{q}(((A + 1)0^{k+1})_{q}) = s_{q}(A + 1).

Suppose

s_{q}(A) + (q − 1) · (k + 1) ≡ α (mod (q − 1) · k + l)  (5)

and

s_{q}(A + 1) ≡ β (mod (q − 1) · k + l),  (6)

where α, β ∈ {0, 1, 2, …, (q − 1) · k + l − 1}. Since every number F in the sequence shown in (4) satisfies s_{q}(F) ≢ 0 (mod n), we indeed have

α, β ∈ {1, 2, …, (q − 1) · k + l − 1}.  (7)

Then the digit sums of the second part of the sequence shown in (4) are contained in the following n − β numbers:

s_{q}(A + 1), …, s_{q}(A + 1) + (q − 1) · k + l − 1 − β.  (8)

The digit sums of the first part of the sequence shown in (4) are contained in the following α numbers:

s_{q}(A) + (q − 1) · (k + 1) − α + 1, …, s_{q}(A) + (q − 1) · (k + 1).  (9)

By Lemma 9, we have s_{q}(A) = s_{q}(A + 1) + (q − 1) · 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 (5) that

s_{q}(A + 1) + (q − 1) · x − 1 + (q − 1) · (k + 1) ≡ α (mod (q − 1) · k + l).

Combining with (6), we have

β − α + (q − 1) · (x + k + 1) − 1 ≡ 0 (mod (q − 1) · k + l).  (10)

According to Lemma 7, (10) has a positive integer solution if and only if gcd(q − 1, (q − 1) · k + l)|α + 1 − β, namely

gcd(q − 1, l)|α + 1 − β.  (11)

A quick inspection of (7) reveals α+1−β ≤ (q−1)·k+l−1. Note that (q−1)·k+r is the largest integer which is divisible by gcd(q − 1, l) and not larger than (q − 1) · k + l − 1. Thus, combining with (7) and (11), it is easy to see that α + 1 − β is not larger than (q − 1) · k + r. Next, in order to get a contradiction, we will estimate the lengths of the two parts of the sequence shown in (4).

(I). We will apply Lemma 8 (1) to the second part of the sequence. Combining with Lemma 11, 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 (8) we know

s_{q}(X) = s_{q}(((A + 1)X)_{q}) − s_{q}(A + 1)
≤ s_{q}(A + 1) + (q − 1) · k + l − 1 − β − s_{q}(A + 1)
= (q − 1) · k + l − 1 − β  (12)
:= (q − 1) · m + β_{1},  (13)

where m ≤ k and β_{1} ∈ {0, 1, …, q − 2}. Note that the least value of s_{q}(X) is 0. Therefore, by Lemma 8 (1), we can obtain that the length of the second part of the sequence is at most ((β_{1} + 1)(q − 1)^{m})_{q}.

(II). We will apply Lemma 8 (2) to the first part of the sequence. Combining with Lemma 11, 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 (9), we have

s_{q}(Y) = s_{q}((AY)_{q}) − s_{q}(A)
≥ s_{q}(A) + (q − 1) · (k + 1) − α + 1 − s_{q}(A)
= (q − 1) · (k + 1) − α + 1.

Let α = (q − 1) · t + h, where t ≤ k and h ∈ {0, 1, …, q − 2}. Since Y ends up with (q − 1)^{k+1}, by Lemma 8 (2), the length of the first part of the sequence must be at most h(q − 1)^{t}.

Summing up the above, we obtain the length of this sequence is at most

((β_{1} + 1)(q − 1)^{m})_{q} + (h(q − 1)^{t})_{q}.

Since (h(q − 1)^{t})_{q} < ((q − 1)^{k})_{q} for t ≤ k − 1, we should let t = k to make ((β_{1} + 1)(q − 1)^{m})_{q} +(h(q−1)^{t})_{q} as large as possible. And then, we obtain from (II) that h = α−(q−1)·k.

Since ((β_{1} + 1)(q − 1)^{m})_{q} ≤ ((q − 1)^{k−1})_{q} < ((q − 1)^{k})_{q} for m ≤ k − 2, we should take m ∈ {k − 1, k} to make ((β_{1} + 1)(q − 1)^{m})_{q} + (h(q − 1)^{t})_{q} as large as possible.

If l = 0, (12) and (13) imply m ≤ k − 1 and thus we should let m = k − 1. Then, we obtain from (I) that q − 1 − 1 − β = β_{1} ≤ q − 2. Hence, ((β_{1} + 1)(q − 1)^{m})_{q} ≤ ((q − 1)^{k})_{q}. To make ((β_{1} + 1)(q − 1)^{m})_{q} + (h(q − 1)^{t})_{q} as large as possible, we should take β_{1} = q − 2. And in this case, β = l = 0.

If l ≥ 1, (12) and (13) imply m ≤ k and thus we should let m = k. Then, we obtain from (I) that l − 1 − β = β_{1} ≥ 0.

Note that in both cases, we have

((β_{1} + 1)(q − 1)^{m})_{q} + (h(q − 1)^{t})_{q} = ((l − β)(q − 1)^{k})_{q} + ((α − (q − 1) · k)(q − 1)^{k})_{q}
= ((l + α + 1 − β − (q − 1) · k)(q − 1)^{k})_{q} − 1
≤ ((l + r)(q − 1)^{k})_{q} − 1 = M_{q,n} − 1,  (14)

which is a contradiction. The proof in Step 1 is completed.

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 3, and thus the numbers 1, 2, …, (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 · (q − 1) + l. So we only need to explain the case of l − 1 ≥ 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

\underbrace{((q − 1)^{x}(q − 1 − r)0^{k−1}1)_{q}, …, ((q − 1)^{x+1+k})_{q}}_{the first part}, \underbrace{(10^{x+1+k})_{q}, …, (10^{x}(l − 1)(q − 1)^{k−1}(q − 2))_{q}}_{the second part}

(15)

contain no integer whose digit sum is divisible by n.

The sums of digits of the integers in the first part shown in (15) are contained in (q − 1) · x + q − r, …, (q − 1) · (x + 1 + k), which equal to 1, 2, …, (q − 1) · k + r modulo n according to Eq. (3).

The sums of digits of the integers in the second part shown in (15) are contained in 1, …, (q − 1) · k + l − 1, which equal to 1, 2, …, (q − 1) · k + l − 1 modulo n by Eq. (3).

Step 3. To complete our proof, it remains to show that (15) 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 ≥ gcd(q − 1, l).

In this step, the length of the sequence is M_{q,n} − 1. So in inequality (14), ((β_{1} + 1)(q − 1)^{m})_{q} + (h(q − 1)^{t})_{q} = M_{q,n} − 1, which means

α + 1 − β = (q − 1) · k + r.  (16)

Combining with (10), we have

(q − 1) · (x + 1) − r ≡ 0 (mod (q − 1) · k + l).  (17)

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 (16) implies that α = (q − 1) · k + r + β − 1 ≥ (q − 1) · k + r. So, we may assume that α = (q − 1) · k + r′, where r′ ∈ {0, 1, …, l − 1}. Then we can simplify (5) further to

s_{q}(A) + q − 1 − r′ ≡ 0 (mod (q − 1) · k + l).  (18)

Together with (17), (18) 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.

Proof of Theorem 5. 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) ≡ j (mod n). For simplicity, we use m_{1}, m_{2}, …, 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 = ∑_{k=1}^{n−j} q^{k+c}. Then s_{q}(m_{i}) + n − j = s_{q}(m_{i} + b),

i ∈ {1, 2, …, M_{q,n}}.

Note that s_{q}(m_{i}) ≠ j (mod n) means s_{q}(m_{i}+b) ≠ 0 (mod 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) ≡ 0 (mod n), which is a contradiction with Theorem 4.

3 Further conclusions and open problems

From Theorem 4, it is easy to obtain the special results below.

Corollary 12 (Binary system case). M_{2,n} = 2^{n} − 1.

Corollary 13 (Decimalism case). Let n = 9 · k + l, k ∈ ℕ, and l ∈ {1, 2, 3, 4, 5, 6, 7, 8, 9}, and then we have M_{10,n} = (M_{10,l} + 1) · 10^{k} − 1. The details are presented in Table 1.

l M_{10,9k+l} example on k = 0 example on k ∈ ℤ^{+}
1 (19^{k})_{10}  (1)_{10}  (1)_{10}
2 (39^{k})_{10}  (9)_{10}  (9^{4k}80^{k−1}1)_{10}
3 (39^{k})_{10}  (1)_{10}  (1)_{10}
4 (79^{k})_{10}  (997)_{10}  (9^{6k+2}60^{k−1}1)_{10}
5 (99^{k})_{10}  (6)_{10}  (9^{k}50^{k−1}1)_{10}
6 (99^{k})_{10}  (7)_{10}  (9^{k}60^{k−1}1)_{10}
7 (139^{k})_{10}  (994)_{10}  (9^{3k+2}30^{k−1}1)_{10}
8 (159^{k})_{10}  (9999993)_{10}  (9^{7k+6}20^{k−1}1)_{10}
9 (99^{k})_{10}  (1)_{10}  (1)_{10}

Table 1: This table is a detailed explanation about Corollary 13, in which we symbolically set (19^{0})_{10} = 1, and the third and fourth columns of this table are the concrete realizations of Eq. (2).

Corollary 13 is a general form of Examples 1 and 2. To illustrate Table 1, we show two examples:

For l = 8 and k = 0, we obtain from Table 1 that M_{10,8} = 15 and the 14 numbers, 9999993, 9999994, …, 10000006, are the smallest 14 consecutive positive integers whose digit sums are all not divisible by 8.

For l = 6 and k = 1, Table 1 shows that M_{10,15} = 99 and the 98 numbers, 961, 962, …, 1058, are the smallest 98 consecutive positive integers whose digit sums are all not divisible by 15.

Finally, we give some open problems.

1. How to extend the method in this paper to prove results about (s_{q}(ak) mod n)_{k=1}^{∞} for given integers q, n, a ≥ 2?

2. How often do M_{q,n} consecutive terms in t_{q,n} cover {0, 1, …, n − 1}?

References

[1] J. F. Morgenbesser, J. Shallit and T. Stoll, Thue-Morse at multiples of an integer, J. Number Theory. 131 (2011), 1498–1512.

[2] J.-P. Allouche and J. Shallit, Sums of digits, overlaps, and palindromes, Discrete Math. Theor. Comput. Sci. 4 (2000), 1–10.

2010 Mathematics Subject Classification: 11B99, 11Y55, 11N25, 11A63, 68R15.

Keywords: digit sum, Thue-Morse sequence. (Concerned with sequences \underline{A010060} and \underline{A141803}.) Received April 12 2016; revised version received July 24 2016; August 31 2016; January 7 2017. Published in Journal of Integer Sequences, January 7 2017. Return to Journal of Integer Sequences home page.