Exact Formulas for the Number of Palindromes in Certain Arithmetic Progressions

Kritkhajohn Onphaeng Faculty of Science and Technology Princess of Naradhiwas University

Naratiwat 96000

Thailand

kritkhajohn.o@pnu.ac.th,
dome3579@gmail.com

Phakhinkon Napp Phunphayap^{*}

Department of Mathematics Faculty of Science Burapha University

Chonburi 20131

Thailand

phakhinkon.ph@go.buu.ac.th,
phakhinkon@gmail.com

Tammatada Khemaratchatakumthorn Department of Mathematics Faculty of Science Silpakorn University Nakhon Pathom 73000 Thailand

                            tammatada@gmail.com,
                       khemaratchataku.t@silpakorn.edu

Prapanpong Pongsriiam Department of Mathematics Faculty of Science Silpakorn University Nakhon Pathom 73000 Thailand and Graduate School of Mathematics Nagoya University Nagoya 464-8602 Japan

                            prapanpong@gmail.com,
                         pongsriiam p@silpakorn.edu

Abstract

A positive integer n is a b-adic palindrome if the representation of n in base b reads the same backward as forward. In this article, we obtain exact formulas for the number of b-adic palindromes that are less than or equal to m and are congruent to r modulo q when b is congruent to 0 or 1 mod q. This extends Pongsriiam and Subwattanachai’s result (done only for q ≤ 2), and supplements Col’s theorem, which is restricted to the case that b(b^{2} − 1) is coprime to q.

*Phakhinkon Napp Phunphayap is the corresponding author.

1 Introduction

Let b ≥ 2, m, n, q ≥ 1, and 0 ≤ r < q be integers. We call n a palindrome in base b (or b-adic palindrome) if the b-adic expansion of n = (a_{k}a_{k−1} ⋯ a_{0})_{b} with a_{k} ≠ 0 has the symmetric property a_{k−i} = a_{i} for 0 ≤ i ≤ k. We let P_{b} be the set of all b-adic palindromes and P_{b}(m) the set of all b-adic palindromes not exceeding m. The 2-adic and 10-adic palindromes are, respectively, \underline{A006995} and \underline{A002113} in OEIS [21]. As usual, if we write a number without specifying the base, then it is always in base 10, and if we write n = (a_{k}a_{k−1} ⋯ a_{0})_{b}, then it means that n = ∑_{i=0}^{k} a_{i}b^{i}, a_{k} ≠ 0, and 0 ≤ a_{i} < b for all i = 0, 1, …, k. So, for example, 9 = (1001)_{2} = (100)_{3} is a palindrome in bases 2 and 10 but not in base 3. In addition, let P_{b}(m, q, r) be the set of all b-adic palindromes that are at most m and are congruent to r modulo q. Finally, let A_{b}(m) = |P_{b}(m)| and A_{b}(m, q, r) = |P_{b}(m, q, r)|, that is,

A_{b}(m, q, r) = ∑_{\begin{matrix}n∈P_{b}(m) \\ n ≡ r (mod q) \end{matrix}} 1.

In recent years, there has been an increasing interest in the study of palindromes. For instance, in 2017, Vepir [23] asked on Mathematics Stack Exchange which number base contains the most palindromic numbers. Pongsriiam and Subwattanachai [18] started the investigation by determining an exact formula for A_{b}(m), but the formula is not easy to analyze, and so it is not enough to answer Vepir’s question. After that, Phunphayap and Pongsriiam [15] showed that if b_{1} > b_{2} ≥ 2 and s_{b} denotes the reciprocal sum of all b-adic palindromes, then s_{b_{1}} and s_{b_{2}} converge and s_{b_{1}} > s_{b_{2}}. Later, they also applied Pongsriiam and Subwattanachai’s exact formula [18] to answer Vepir’s question that in fact, A_{b}(n) − A_{b_{1}}(n) has infinitely many sign changes when n ranges over all positive integers and b, b_{1} are distinct integers larger than 1.

Moreover, Harminc and Soták [11] studied palindromes in arithmetic progressions and proved that for a, b ≥ 2, d ∈ ℕ, there are infinitely many b-adic palindromes that are congruent to a mod d if and only if b ∤ a or b ∤ d. Col [8] extended Harminc and Soták’s result and obtained some distributional theorems concerning A_{b}(m, q, r) and A_{b}(m)/q for all b ≥ 2 satisfying gcd(q, b(b^{2} − 1)) = 1. In 2015, Pálvölgyi (aka “Domotorp”) asked on Math-Overflow [14] whether or not there exists an arbitrarily long arithmetic progression whose members are palindromes. Tao [22] gave a negative answer to Pálvölgyi’s question, and from his comments, it seems that arithmetic progressions of palindromes should have length no more than 10^{8}. Pongsriiam [17] then proved that the length of an arithmetic progression of palindromes (in base 10) is at most 10.

In this article, we consider palindromes in arithmetic progressions and obtain exact formulas for A_{b}(m, q, r) where b ≡ 0, 1 (mod q). This improves Pongsriiam and Subwattanachai’s result, which focuses only on the case q ≤ 2. It also supplements Col’s theorem, which is restricted to the case gcd(q, b(b^{2} − 1)) = 1.

For more information on the palindromes, we refer the reader to Banks [1], Cilleruelo, Luca, and Baxter [6], and Rajasekaran, Shallit, and Smith [19] for additive properties of palindromes, Banks, Hart, and Sakata [2] and Banks and Shparlinski [3] for some multiplicative properties of palindromes, Bas̆ić [4, 5], Di Scala and Sombra [20], Goins [10], Luca and Togbé [13] for the study of palindromes in different bases, Cilleruelo, Luca, and Tesoro [7] for palindromes in linear recurrence sequences, and Korec [12] for nonpalindromic numbers having palindromic squares.

2 Preliminaries and lemmas

In this section, we provide some definitions and lemmas that are needed in the proof of the main theorems. Recall that for a real number x, ⌊x⌋ is the largest integer less than or equal to x and ⌈x⌉ is the smallest integer greater than or equal to x. In addition, we write a mod m to denote the least nonnegative residue of a modulo m. We also use the Iverson notation: if P is a mathematical statement, then

[P] = \begin{cases}1, & if P holds; \\ 0, & otherwise. \end{cases}

Throughout this article, the empty sum is defined to be zero. It is also convenient to define C_{b}(m) for each m ∈ ℕ as follows:

Definition 1. Let b ≥ 2 and m = (a_{k}a_{k−1} ⋯ a_{1}a_{0})_{b} be positive integers. We define C_{b}(m) = (c_{k}c_{k−1} ⋯ c_{1}c_{0})_{b} to be the b-adic palindrome satisfying c_{i} = a_{i} for k − ⌊k/2⌋ ≤ i ≤ k. In other words, C_{b}(m) is the b-adic palindrome having k +1 digits whose first half digits are the same as those of m in its b-adic expansion, that is, C_{b}(m) = (a_{k}a_{k−1} ⋯ a_{k−⌊k/2⌋} ⋯ a_{k−1}a_{k})_{b}.

For example, if m = (134240)_{5} = (12702)_{8}, then C_{5}(m) = (134431)_{5} and C_{8}(m) = (12721)_{8}. In the next lemma and throughout this article, we let s_{b}(n) be the sum of digits of n in base b, that is, if n = (a_{k}a_{k−1} ⋯ a_{0})_{b}, then s_{b}(n) = ∑_{0≤i≤k} a_{i}.

Lemma 2. Let b, n, q, r be integers, b ≥ 2, n, q ≥ 1, and n = (a_{k}a_{k−1} ⋯ a_{1}a_{0})_{b}. Then the following statements hold.

(i) Assume that b ≡ 0 (mod q). Then n ≡ r (mod q) if and only if a_{0} ≡ r (mod q).

(ii) Assume that b ≡ 1 (mod q). Then n ≡ r (mod q) if and only if s_{b}(n) ≡ r (mod q).

Proof. For (i), we have n = ∑_{0≤j≤k} a_{j}b^{j} ≡ a_{0} (mod q), which implies that n ≡ r (mod q) if and only if a_{0} ≡ r (mod q). For (ii), we have

n = ∑_{0≤j≤k} a_{j}b^{j} ≡ ∑_{0≤j≤k} a_{j} (mod q),

which implies the desired result.

It is convenient to have a lemma that gives the number of positive integers n ≤ x lying in a residue class a mod q. It is also useful to define the following function.

Definition 3. Let b, q, k ∈ ℕ and r, x, y ∈ ℤ. We define N_{b}(k, q, r, x, y) to be the number of integer solutions to the congruence

x_{1} + x_{2} + ⋯ + x_{k} ≡ r (mod q),

where x ≤ x_{1} < y and 0 ≤ x_{i} < b for each i = 2, 3, …, k. In addition, we let

N_{b}(k, q, r) = N_{b}(k, q, r, 0, b).

Lemma 4. Let a, q ∈ ℕ and r ∈ ℤ. Then

∑_{\begin{matrix}0≤n<a \\ n ≡ r (mod q) \end{matrix}} 1 = ⌊a/q⌋ + [r mod q < a mod q].

Proof. We can assume that 0 ≤ r < q. Let s = a mod q and write a = ℓq + s for some ℓ ∈ ℕ_{0}. If r < s, then there are ℓ + 1 = ⌊a/q⌋ + 1 choices for n ∈ {r, q + r, 2q + r, …, ℓq + r}. Similarly, If r ≥ s, there are ℓ = ⌊a/q⌋ choices for n ∈ {r, q + r, 2q + r, …, (ℓ − 1)q + r}. In any case, there are ⌊a/q⌋ + [r < s] possible values for n. This completes the proof.

The next lemma is an important tool in obtaining the main results. Recall that, throughout this article, we write a mod m to denote the least nonnegative residue of a modulo m.

Lemma 5. Let a, b, k, q, r ∈ ℤ and a, b, k, q ≥ 1. Assume that b ≡ 1 (mod q). Then the following statements hold.

(i) N_{b}(k, q, r) = \frac{b^{k}−1}{q} + [r ≡ 0 (mod q)].

(ii) N_{b}(k, q, r, 1, b) = \frac{b^{k}−b^{k−1}}{q}.

(iii) N_{b}(k, q, r, 0, a) = \frac{a(b^{k−1}−1)}{q} + ⌊a/q⌋ + [r mod q < a mod q].

(iv) N_{b}(k, q, r, 1, a) = \frac{(a−1)(b^{k−1}−1)}{q} + ⌊a/q⌋ + [r mod q < a mod q] − [r ≡ 0 (mod q)].

Proof. We can assume that 0 ≤ r < q and let s = a mod q. We prove (i) by induction on k. Since b ≡ 1 (mod q), we obtain by Lemma 4 that

N_{b}(1, q, r) = ∑_{\begin{matrix}0≤x<b \\ x ≡ r (mod q) \end{matrix}} 1 = ⌊b/q⌋ + [r < 1] = \frac{b − 1}{q} + [r = 0].

Next, we let k ≥ 1 be integers and assume that N_{b}(k, q, r) = (b^{k} − 1)/q + [r = 0]. Since

x_{1} + ⋯ + x_{k} + x_{k+1} ≡ r (mod q) if and only if x_{1} + ⋯ + x_{k} ≡ r − x_{k+1} (mod q),

we see that

N_{b}(k + 1, q, r) = ∑_{0≤x_{k+1}<b} N_{b} (k, q, (r − x_{k+1}) mod q)

= ∑_{0≤x_{k+1}<b} (\frac{b^{k} − 1}{q} + [r − x_{k+1} ≡ 0 (mod q)])

= \frac{b (b^{k} − 1)}{q} + ∑_{0≤x_{k+1}<b}[x_{k+1} ≡ r (mod q)]

= \frac{b (b^{k} − 1)}{q} + N_{b}(1, q, r)

= \frac{b (b^{k} − 1)}{q} + \frac{b − 1}{q} + [r = 0]

= \frac{b^{k+1} − 1}{q} + [r = 0].

This proves (i). For (ii), if k = 1, then we obtain by Lemma 4 that

N_{b}(k, q, r, 1, b) = ∑_{\begin{matrix}0≤x<b \\ x ≡ r (mod q) \end{matrix}} 1 − [r = 0] = ⌊b/q⌋ + [r < 1] − [r = 0] = \frac{b − 1}{q}.

If k ≥ 2, then we obtain by (i) that

N_{b}(k, q, r, 1, b) = N_{b}(k, q, r) − N_{b}(k − 1, q, r) = \frac{b^{k} − b^{k−1}}{q} .

For (iii), we obtain by Lemma 4 that

N_{b}(1, q, r, 0, a) = ∑_{\begin{matrix}0≤x<a \\ x ≡ r (mod q) \end{matrix}} 1 = ⌊a/q⌋ + [r < s].

Now, suppose k ≥ 2. We first fix 0 ≤ x_{1} < a and then count the remaining x_{i}. From (i) and Lemma 4, we obtain that

N_{b}(k, q, r, 0, a) = ∑_{0≤x_{1}<a} N_{b}(k − 1, q, (r − x_{1}) mod q)

= ∑_{0≤x_{1}<a} (\frac{b^{k−1} − 1}{q} + [x_{1} ≡ r (mod q)])

= \frac{a(b^{k−1} − 1)}{q} + ⌊a/q⌋ + [r < s],

as desired. For (iv), if k = 1, then

N_{b}(1, q, r, 1, a) = N_{b}(1, q, r, 0, a) − [r ≡ 0 (mod q)] = ⌊a/q⌋ + [r < s] − [r = 0]. If k ≥ 2, then we obtain by (i) and (iii) that

N_{b}(k, q, r, 1, a) = N_{b}(k, q, r, 0, a)−N_{b}(k−1, q, r) = \frac{(a − 1)(b^{k−1} − 1)}{q}+⌊a/q⌋+[r < s]−[r = 0].

This completes the proof.

We will deal with some calculations involving the floor function. So it is useful to recall the following results, which will be applied throughout this article sometimes without reference. Lemma 6. For k ∈ ℤ and x ∈ ℝ, the following statements hold.

(i) ⌊k + x⌋ = k + ⌊x⌋, (ii) {k + x} = {x},

(iii) ⌊x⌋ + ⌊−x⌋ = \begin{cases}−1, & if x ∉ ℤ; \\ 0, & if x ∈ ℤ, \end{cases}

(iv) 0 ≤ {x} < 1 and {x} = 0 if and only if x ∈ ℤ.

(v) ⌊x + y⌋ = \begin{cases}⌊x⌋ + ⌊y⌋, & if \{x\} + \{y\} < 1; \\ ⌊x⌋ + ⌊y⌋ + 1, & if \{x\} + \{y\} ≥ 1, \end{cases}

(vi) ⌊⌊x⌋/k⌋ = ⌊x/k⌋ for k ≥ 1. Proof. These are well-known and can be proved easily. For more details, see in the books by Graham, Knuth, and Patashnik [9, Chapter 3] and Pongsriiam [16, Chapter 3].

3 Main results

In this section, we determine the formula for A_{b}(m, q, r) where b ≡ 0 or 1 (mod q). Since the case b ≡ 0 (mod q) is easier than the other case, we begin with b ≡ 0 (mod q) as follows.

3.1 The case b ≡ 0 (mod q)

Theorem 7. Let b ≥ 2 and m, q ≥ 1 be integers, and b ≡ 0 (mod q). Let

m = (a_{k}a_{k−1} ⋯ a_{1}a_{0})_{b} and α = α_{m} = \frac{b^{⌈k/2⌉} + b^{⌊k/2⌋} − 2}{b − 1}.

Then A_{b}(m, q, 0) is equal to

(\frac{b}{q} − 1) α+⌊\frac{a_{k} − 1}{q}⌋ b^{⌊k/2⌋}+[a_{k} ≡ 0 (mod q)] ( ∑_{1≤i≤⌊k/2⌋} a_{k−i}b^{⌊k/2⌋−i} + [m ≥ C_{b}(m)]) , (1)

and if r mod q > 0, then A_{b}(m, q, r) is equal to

\frac{bα}{q} + ⌈\frac{a_{k} − (r mod q)}{q}⌉ b^{⌊k/2⌋} + [a_{k} ≡ r (mod q)] ( ∑_{1≤i≤⌊k/2⌋} a_{k−i}b^{⌊k/2⌋−i} + [m ≥ C_{b}(m)]) .

(2)

Proof. Throughout this proof, we apply Lemma 2(i) repeatedly without reference. We can assume that 0 ≤ r < q and let

m^{∗} = ∑_{0≤i≤⌊k/2⌋} a_{k−i}b^{k−i} = (a_{k}a_{k−1} ⋯ a_{k−⌊k/2⌋}00 ⋯ 0)_{b}.

Since b ≡ 0 (mod q), there exists an integer ℓ ≥ 1 such that b = ℓq. We have

A_{b}(m, q, r) = ∑_{\begin{matrix}n∈P_{b}(m) \\ n ≡ r (mod q) \end{matrix}} 1 = ∑_{\begin{matrix}n∈P_{b} \\ n ≡ r (mod q) \\ n < b^{k} \end{matrix}} 1 + ∑_{\begin{matrix}n∈P_{b} \\ n ≡ r (mod q) \\ b^{k} ≤ n < a_{k}b^{k} \end{matrix}} 1 + ∑_{\begin{matrix}n∈P_{b} \\ n ≡ r (mod q) \\ a_{k}b^{k} ≤ n < m^{∗} \end{matrix}} 1 + ∑_{\begin{matrix}n∈P_{b} \\ n ≡ r (mod q) \\ m^{∗} ≤ n ≤ m \end{matrix}} 1. (3)

In the first and second rightmost sum in (3), we see that if a_{k}b^{k} ≤ n ≤ m, then the leftmost digit of n in its b-adic expansion is a_{k} = a_{0}. Therefore (3) implies that

A_{b}(m, q, r) = ∑_{\begin{matrix}n∈P_{b} \\ n ≡ r (mod q) \\ n < b^{k} \end{matrix}} 1 + ∑_{\begin{matrix}n∈P_{b} \\ n ≡ r (mod q) \\ b^{k} ≤ n < a_{k}b^{k} \end{matrix}} 1 + [a_{k} ≡ r (mod q)] ( ∑_{\begin{matrix}n∈P_{b} \\ a_{k}b^{k} ≤ n < m^{∗} \end{matrix}} 1 + ∑_{\begin{matrix}n∈P_{b} \\ m^{∗} ≤ n ≤ m \end{matrix}} 1) .

(4)

We divide the calculation into 4 parts according to the sums appearing on the right-hand side of (4).

Part 1 We calculate the first sum on the right-hand side of (4) and divide the consideration into two cases depending on r.

Case 1.1 r = 0. We first show that

∑_{\begin{matrix}n∈P_{b} \\ n ≡ 0 (mod q) \\ b^{t} ≤ n < b^{t+1} \end{matrix}} 1 = (\frac{b}{q} − 1) b^{⌊t/2⌋} for all integers t ≥ 0.  (5)

Let t ≥ 0 be an integer. The left-hand side of (5) counts the number of b-adic palindromes that have t+1 digits in their b-adic expansion and are congruent to 0 modulo q. Since b = ℓq, such the numbers are of the form n = (c_{t}c_{t−1} ⋯ c_{1}c_{0})_{b} where c_{t} ∈ {q, 2q, …, (ℓ − 1)q}, c_{i} ∈ {0, 1, 2, …, b − 1}, and c_{i} = c_{t−i} for all i ∈ {0, 1, 2, …, ⌊t/2⌋}. So there are ℓ − 1 = (b/q − 1) choices for c_{t} and, after c_{t} is chosen, there is only one choice for c_{0} = c_{t}. There are b possible values for c_{t−1} ∈ {0, 1, …, b − 1} and there is one possible value for c_{1} = c_{t−1}. In general, there are b choices for c_{t−i} for 1 ≤ i ≤ ⌊t/2⌋ and exactly one choice for the corresponding c_{i}. Therefore

∑_{\begin{matrix}n∈P_{b} \\ n ≡ 0 (mod q) \\ b^{t} ≤ n < b^{t+1} \end{matrix}} 1 = (\frac{b}{q} − 1) · \underbrace{b · b ⋯ b}_{⌊t/2⌋ terms} = (\frac{b}{q} − 1) b^{⌊t/2⌋}.

This proves (5). Then (5) implies that

∑_{\begin{matrix}n∈P_{b} \\ n ≡ 0 (mod q) \\ 1 ≤ n < b^{k} \end{matrix}} 1 = ∑_{i=0}^{k−1} ∑_{\begin{matrix}n∈P_{b} \\ n ≡ 0 (mod q) \\ b^{i} ≤ n < b^{i+1} \end{matrix}} 1 = ∑_{i=0}^{k−1} (\frac{b}{q} − 1) b^{⌊i/2⌋} = (\frac{b}{q} − 1) ∑_{1≤i≤k} b^{⌊(i−1)/2⌋}. (6)

If k is even, then (6) is

(\frac{b}{q} − 1) (2 + 2b + ⋯ 2b^{(k−2)/2}) = 2 (\frac{b}{q} − 1) \frac{b^{k/2} − 1}{b − 1} = (\frac{b}{q} − 1) \frac{b^{⌈k/2⌉} + b^{⌊k/2⌋} − 2}{b − 1}.

Similarly, if k is odd, then (6) becomes

(\frac{b}{q} − 1) (2 + 2b + ⋯ + 2b^{(k−3)/2} + b^{(k−1)/2}) = (\frac{b}{q} − 1) (\frac{2 (b^{(k−1)/2} − 1) + (b − 1)b^{(k−1)/2}}{b − 1} )

= (\frac{b}{q} − 1) \frac{b^{⌈k/2⌉} + b^{⌊k/2⌋} − 2}{b − 1}.

From the above observation and (6), we obtain

∑_{\begin{matrix}n∈P_{b} \\ n ≡ 0 (mod q) \\ 1 ≤ n < b^{k} \end{matrix}} 1 = (\frac{b}{q} − 1) \frac{b^{⌈k/2⌉} + b^{⌊k/2⌋} − 2}{b − 1} = (\frac{b}{q} − 1) α.  (7)

Case 1.2 r ≠ 0. Similar to Case 1, we first show that

∑_{\begin{matrix}n∈P_{b} \\ n ≡ r (mod q) \\ b^{t} ≤ n < b^{t+1} \end{matrix}} 1 = \frac{b^{1+⌊t/2⌋}}{q} for all integers t ≥ 0.  (8)

Let t ≥ 0 be an integer and n = (c_{t}c_{t−1} ⋯ c_{1}c_{0})_{b} a b-adic palindrome that is counted in the left-hand side of (8). Then c_{t} ∈ {r, q + r, 2q + r, …, (ℓ − 1)q + r}, c_{i} ∈ {0, 1, 2, …, b − 1}, and c_{i} = c_{t−i} for all i ∈ {0, 1, 2, …, ⌊t/2⌋}. So there are ℓ = b/q possible values for c_{t} and there is only one possible value for c_{0}. For each 1 ≤ i ≤ ⌊t/2⌋, there are b choices for c_{t−i} and exactly one choice for the corresponding c_{i}. This leads to

∑_{\begin{matrix}n∈P_{b} \\ n ≡ r (mod q) \\ b^{t} ≤ n < b^{t+1} \end{matrix}} 1 = \frac{b}{q} · \underbrace{b · b ⋯ b}_{⌊t/2⌋ terms} = \frac{b^{1+⌊t/2⌋}}{q} .

Therefore

∑_{\begin{matrix}n∈P_{b} \\ n ≡ r (mod q) \\ 1 ≤ n < b^{k} \end{matrix}} 1 = ∑_{i=0}^{k−1} ∑_{\begin{matrix}n∈P_{b} \\ n ≡ r (mod q) \\ b^{i} ≤ n < b^{i+1} \end{matrix}} 1 = ∑_{i=0}^{k−1} \frac{b^{1+⌊i/2⌋}}{q} = \frac{b}{q} ∑_{1≤i≤k} b^{⌊(i−1)/2⌋}.  (9)

The right-hand side of (9) can be evaluated in a similar way as (6), which leads to

∑_{\begin{matrix}n∈P_{b} \\ n ≡ r (mod q) \\ 1 ≤ n < b^{k} \end{matrix}} 1 = \frac{bα}{q}.  (10)

Part 2 We calculate the second sum on the right-hand side of (4), and divide the calculation into two cases.

Case 2.1 r = 0. We show that

∑_{\begin{matrix}n∈P_{b} \\ n ≡ 0 (mod q) \\ b^{k} ≤ n < a_{k}b^{k}. \end{matrix}} 1 = ⌊\frac{a_{k} − 1}{q}⌋ b^{⌊k/2⌋}.  (11)

The left-hand side of (11) counts the integers of the form n = (c_{k}c_{k−1} ⋯ c_{1}c_{0})_{b} where

1 ≤ c_{k} < a_{k}, c_{k} ≡ 0 (mod q), c_{i} ∈ {0, 1, 2, …, b − 1}, and c_{i} = c_{k−i},

for all i ∈ [0, ⌊k/2⌋]∩ℤ. We write a_{k} = xq+y where x, y ∈ ℤ and 0 ≤ y < q. Since 1 ≤ a_{k} < b and b = ℓq, we have 0 ≤ x ≤ ℓ − 1. If y = 0, then x ≥ 1 and c_{k} ∈ {q, 2q, …, (x − 1)q}, and so there are

x − 1 = ⌊\frac{xq − 1}{q}⌋ = ⌊\frac{a_{k} − 1}{q}⌋ possible values for c_{k}.

If 1 ≤ y < q, then c_{k} ∈ {q, 2q, …, xq}, so there are x = ⌊(xq + y − 1)/q⌋ = ⌊(a_{k} − 1)/q⌋ possible values for c_{k}. In any case, there are ⌊(a_{k} − 1)/q⌋ possible values for c_{k}, and after c_{k} is chosen, there is only one possible value for c_{0} = c_{k}. There are b choices for c_{k−i} for 1 ≤ i ≤ ⌊k/2⌋ and exactly one choice for the corresponding c_{i}. Therefore

∑_{\begin{matrix}n∈P_{b} \\ n ≡ 0 (mod q) \\ b^{k} ≤ n < a_{k}b^{k+1} \end{matrix}} 1 = ⌊\frac{a_{k} − 1}{q}⌋ · \underbrace{b · b ⋯ b}_{⌊k/2⌋ terms} = ⌊\frac{a_{k} − 1}{q}⌋ b^{⌊k/2⌋}.

Case 2.2 r ≠ 0. This case is similar to Case 1. We show that

∑_{\begin{matrix}n∈P_{b} \\ n ≡ r (mod q) \\ b^{k} ≤ n < a_{k}b^{k}. \end{matrix}} 1 = ⌈\frac{a_{k} − r}{q}⌉ b^{⌊k/2⌋}.  (12)

Let n = (c_{k}c_{k−1} ⋯ c_{1}c_{0})_{b} be a b-adic palindrome that is counted in the left-hand side of (12). Then 1 ≤ c_{k} < a_{k}, c_{k} ≡ r (mod q), c_{i} ∈ {0, 1, 2, …, b − 1}, and c_{i} = c_{k−i} for all i = 0, 1, 2, …, ⌊k/2⌋. We write a_{k} = xq + y where 0 ≤ x ≤ ℓ − 1 and 0 ≤ y < q. If y ≤ r, then c_{k} ∈ {r, q + r, 2q + r, …, (x − 1)q + r}, so there are x = ⌈(xq + y − r)/q⌉ = ⌈(a_{k} − r)/q⌉ possible values for c_{k}. If y > r, then c_{k} ∈ {r, q + r, 2q + r, …, xq + r}, so there are x + 1 = ⌈(xq + y − r)/q⌉ = ⌈(a_{k} − r)/q⌉ possible values for c_{k}. In any case, there are ⌈(a_{k} − r)/q⌉ possible values for c_{k}, and after c_{k} is chosen, there is only one possible value for c_{0}. For each 1 ≤ i ≤ ⌊k/2⌋, there are b choices for c_{k−i} and exactly one choice for the corresponding c_{i}. Therefore

∑_{\begin{matrix}n∈P_{b} \\ n ≡ r (mod q) \\ b^{k} ≤ n < a_{k}b^{k+1} \end{matrix}} 1 = ⌈\frac{a_{k} − r}{q}⌉ · \underbrace{b · b ⋯ b}_{⌊k/2⌋ terms} = ⌈\frac{a_{k} − r}{q}⌉ b^{⌊k/2⌋},

as desired.

Part 3 We compute the third sum in (4). For each j ∈ {0, 1, …, ⌊k/2⌋}, let

m_{j} = ∑_{0≤i≤j} a_{k−i}b^{k−i} = (a_{k}a_{k−1} ⋯ a_{k−j}00 ⋯ 0)_{b}.

Then

∑_{\begin{matrix}n∈P_{b} \\ a_{k}b^{k} ≤ n < m^{∗} \end{matrix}} 1 = ∑_{1≤j≤⌊k/2⌋} ∑_{\begin{matrix}n∈P_{b} \\ m_{j−1}≤n<m_{j} \end{matrix}} 1.  (13)

We first show that for 1 ≤ j ≤ ⌊k/2⌋,

∑_{\begin{matrix}n∈P_{b} \\ m_{j−1}≤n<m_{j} \end{matrix}} 1 = a_{k−j}b^{⌊k/2⌋−j}.  (14)

Let n = (c_{k}c_{k−1} … c_{1}c_{0})_{b} be an integer that is counted in the left-hand side of (14). We see that m_{j−1} = (a_{k}a_{k−1} ⋯ a_{k−(j−1)}00 ⋯ 0)_{b} and m_{j} = (a_{k}a_{k−1} ⋯ a_{k−j}00 ⋯ 0)_{b}. Then there is only one possible value for each c_{k}, c_{k−1}, …, c_{k−j+1}, namely, c_{k} = a_{k}, c_{k−1} = a_{k−1}, …, c_{k−j+1} = a_{k−j+1}. In addition, there is only one choice for each c_{0}, c_{1}, …, c_{j−1} since c_{k−i} = c_{i} for i = 0, 1, …, j − 1. Since c_{k−j} ∈ {0, 1, 2, … a_{k−j} − 1}, there are a_{k−j} choices for c_{k−j}. The remaining digits c_{k−i}, where j + 1 ≤ i ≤ ⌊k/2⌋, can be chosen arbitrarily from 0, 1, …, b − 1. So the left-hand side of (14) is equal to

a_{k−j} · \underbrace{b · b ⋯ b}_{⌊k/2⌋−j terms} = a_{k−j}b^{⌊k/2⌋−j}.

This proves (14). From (13) and (14), we obtain

∑_{\begin{matrix}n∈P_{b} \\ a_{k}b^{k} ≤ n < m^{∗} \end{matrix}} 1 = ∑_{1≤j≤⌊k/2⌋} a_{k−j}b^{⌊k/2⌋−j}.  (15)

Part 4 We calculate the last sum in (4). Recall that m = (a_{k}a_{k−1} ⋯ a_{1}a_{0})_{b} and m^{∗} = (a_{k}a_{k−1} ⋯ a_{k−⌊k/2⌋}00 ⋯ 0)_{b}. The only possible palindrome n such that m^{∗} ≤ n ≤ m is n = C_{b}(m). So the number of such palindromes is 1 if m ≥ C_{b}(m) and is 0 otherwise. That is

∑_{\begin{matrix}n∈P_{b} \\ m^{∗}≤n≤m \end{matrix}} 1 = [m ≥ C_{b}(m)].  (16)

Therefore we obtain the formula (1) from (7), (11), (15), and (16), and the formula (2) from (10), (12), (15), and (16). This completes the proof.

Applying Theorem 7 with q = 1, 2, we obtain Pongsriiam and Subwattanachai’s result [18, Theorems 2.2 and 2.3] as a corollary.

Corollary 8. Let b ≥ 2 and m ≥ 1 be integers and m = (a_{k}a_{k−1} ⋯ a_{1}a_{0})_{b}. Then

A_{b}(m, 1, 0) = A_{b}(m) = b^{⌈k/2⌉} + ∑_{0≤i≤⌊k/2⌋} a_{k−i}b^{⌊k/2⌋−i} + [m ≥ C_{b}(m)] − 2.

In addition, if α = (b^{⌈k/2⌉} + b^{⌊k/2⌋} − 2)/(b − 1), q = 2, and b ≡ 0 (mod 2), then A_{b}(m, 2, 0) is equal to

(\frac{b}{2} − 1) α + ⌊\frac{a_{k} − 1}{2}⌋ b^{⌊k/2⌋} + [a_{k} ≡ 0 (mod 2)] ( ∑_{1≤i≤⌊k/2⌋} a_{k−i}b^{⌊k/2⌋−i} + [m ≥ C_{b}(m)]) ,

and A_{b}(m, 2, 1) is equal to

\frac{bα}{2} + ⌈\frac{a_{k} − 1}{2}⌉ b^{⌊k/2⌋} + [a_{k} ≡ 1 (mod 2)] ( ∑_{1≤i≤⌊k/2⌋} a_{k−i}b^{⌊k/2⌋−i} + [m ≥ C_{b}(m)]) .

3.2 The case b ≡ 1 (mod q)

Theorem 9. Let b ≥ 2, m, q ≥ 1, and 0 ≤ r < q be integers, b ≡ 1 (mod q), and m = (a_{k}a_{k−1} ⋯ a_{1}a_{0})_{b}. For each nonnegative integer j ≤ ⌊k/2⌋, let

r_{j} = \begin{cases}(r − 2 ∑_{0≤i≤(k/2)−1} a_{k−i}) mod q, & if j = k/2; \\ (\frac{r}{2} − ∑_{0≤i≤j−1} a_{k−i}) mod q/2, & if q is even and j ≠ k/2; \\ ((\frac{q+1}{2}) r − ∑_{0≤i≤j−1} a_{k−i}) mod q, & if q is odd and j ≠ k/2, \end{cases} and

s_{j} = \begin{cases}a_{k−j} mod q/2, & if q is even and j ≠ k/2; \\ a_{k−j} mod q, & otherwise. \end{cases}

Let

m_{1}^{∗} = ∑_{0≤j≤(k−1)/2} (\frac{2a_{k−j}b^{((k−1)/2)−j} − 2s_{j}}{q} + [r_{j} < s_{j}]) , m_{2}^{∗} = ∑_{0≤j≤(k/2)−1} \frac{a_{k−j}(b − 1)b^{(k/2)−j−1}}{q} ,

m_{3}^{∗} = ∑_{0≤j≤(k/2)−1} (\frac{a_{k−j}(b + 1)b^{(k/2)−j−1} − 2s_{j}}{q} + [r_{j} < s_{j}]) , and

δ(m) = [m ≥ C_{b}(m)] [r_{⌊k/2⌋} = s_{⌊k/2⌋}] .

Then the following statements hold.

(i) If q is odd, then

A_{b}(m, q, r) = \frac{b^{⌊(k+1)/2⌋} − 1}{q} + ∑_{0≤j≤⌊k/2⌋} (⌊\frac{a_{k−j}b^{⌊k/2⌋−j}}{q} ⌋ + [r_{j} < s_{j}]) − [r = 0] + δ(m).

(ii) If q is even, then A_{b}(m, q, r) is equal to

\frac{(b−1)b^{(k−1)/2}}{q} ,  if k and r are odd;
\frac{(b+1)b^{(k−1)/2}−2}{q} + m_{1}^{∗} − [r = 0] + δ(m),  if k is odd and r is even;
⌊\frac{a_{k/2}}{q} ⌋ + m_{2}^{∗} + [r_{k/2} < s_{k/2}] + δ(m),  if k is even and r is odd;
\frac{2(b^{k/2}−1)}{q} + ⌊\frac{a_{k/2}}{q} ⌋ + m_{3}^{∗} − [r = 0] + [r_{k/2} < s_{k/2}] + δ(m), if k and r are even.

Remark 10. In the proof of this theorem, we also show that [r_{⌊k/2⌋} = s_{⌊k/2⌋}] can be replaced by [s_{b}(C_{b}(m)) ≡ r (mod q)], that is,

δ(m) = [m ≥ C_{b}(m)] [s_{b} (C_{b}(m)) ≡ r (mod q)] .

Proof. If q = 1, then r = 0 and the result follows from Corollary 8. So assume that q ≥ 2. If k = 0, then m = a_{0} where 1 ≤ a_{0} < b, m = C_{b}(m), and we obtain by Lemma 4 that

A_{b}(m, q, r) = ∑_{\begin{matrix}1≤n≤a_{0} \\ n ≡ r (mod q) \end{matrix}} 1 = ∑_{\begin{matrix}0≤n<a_{0} \\ n ≡ r (mod q) \end{matrix}} 1 − [r = 0] + [a_{0} ≡ r (mod q)]

= ⌊a_{0}/q⌋ + [r mod q < a_{0} mod q] − [r = 0] + [r mod q = a_{0} mod q]
= ⌊a_{0}/q⌋ + [r_{0} < s_{0}] − [r = 0] + δ(m).

This proves the case k = 0. For the clarity of the proof, we will also first consider the case k = 1, that is, we have m = (a_{1}a_{0})_{b}. Since b ≡ 1 (mod q), we obtain by Lemma 4 that

A_{b}(m, q, r) = ∑_{\begin{matrix}1≤n<b \\ n ≡ r (mod q) \end{matrix}} 1 + ∑_{\begin{matrix}n∈P_{b} \\ n ≡ r (mod q) \\ b≤n≤m \end{matrix}} 1

= \frac{b − 1}{q} + ∑_{\begin{matrix}n∈P_{b} \\ b≤n<a_{1}b \\ n ≡ r (mod q) \end{matrix}} 1 + ∑_{\begin{matrix}n∈P_{b} \\ a_{1}b≤n≤m \\ n ≡ r (mod q) \end{matrix}} 1.  (17)

The only possible b-adic palindrome that can be counted in the second sum in (17) is (a_{1}a_{1})_{b} = C_{b}(m), and it is actually counted if and only if m ≥ C_{b}(m) and C_{b}(m) ≡ r (mod q). Therefore (17) implies that

A_{b}(m, q, r) = \frac{b − 1}{q} + ∑_{\begin{matrix}n∈P_{b} \\ b≤n<a_{1}b \\ n ≡ r (mod q) \end{matrix}} 1 + δ_{1}(m),  (18)

where δ_{1}(m) = [m ≥ C_{b}(m)][C_{b}(m) ≡ r (mod q)]. The palindromes counted in the sum on the right-hand side of (18) is of the form n = (aa)_{b} where 1 ≤ a < a_{1} and

2a ≡ ab + a = n ≡ r (mod q).  (19)

We divide the consideration into two cases.

Case 1 q is even. If r is odd, then (19) is not possible and the sum on the right-hand side of (18) is equal to 0. Suppose that r is even. Then (19) is equivalent to

a ≡ r/2 (mod q/2).

By Lemma 5, the sum on the right-hand side of (18) is equal to

N_{b} (1, q/2, r/2, 1, a_{1}) = ⌊2a_{1}/q⌋ + [r/2 mod q/2 < a_{1} mod q/2] − [r/2 ≡ 0 (mod q/2)]

= \frac{2a_{1} − 2s_{0}}{q} + [r_{0} < s_{0}] − [r = 0].

Therefore (18) becomes

A_{b}(m, q, r) = \begin{cases}\frac{b−1}{q} + δ_{1}(m), & if r is odd; \\ \frac{b−1}{q} + \frac{2a_{1}−2s_{0}}{q} + [r_{0} < s_{0}] − [r = 0] + δ_{1}(m), & if r is even. \end{cases}

Since C_{b}(m) = a_{1}b + a_{1} ≡ 2a_{1} (mod q), we see that C_{b}(m) ≡ r (mod q) if and only if

2a_{1} ≡ r (mod q).

So, if r is odd, then δ_{1}(m) = 0. If r is even, then the above congruence is equivalent to a_{1} ≡ r/2 (mod q/2), that is, r_{0} = s_{0}, and so δ_{1}(m) = δ(m). Therefore the result follows.

Case 2 q is odd. This case is similar to Case 1, so we skip some details. We see that (19) is equivalent to

a ≡ (\frac{q + 1}{2}) r (mod q).

In addition, C_{b}(m) ≡ r (mod q) if and only if a_{1} ≡ (q + 1)r/2 (mod q), that is, r_{0} = s_{0}. Therefore δ_{1}(m) = δ(m) and we obtain from (18) that A_{b}(m, q, r) is equal to

\frac{b − 1}{q} + N_{b} (1, q, (\frac{q + 1}{2}) r, 1, a_{1}) + δ_{1}(m)

= \frac{b − 1}{q} + ⌊a_{1}/q⌋ + [(\frac{q + 1}{2}) r mod q < a_{1} mod q] − [r = 0] + δ(m)

= \frac{b − 1}{q} + ⌊a_{1}/q⌋ + [r_{0} < s_{0}] − [r = 0] + δ(m),

which proves the result.

Hence from this point on, we assume that q, k ≥ 2. We will also apply Lemma 2(ii) repeatedly without reference. Let

m^{∗} = ∑_{0≤i≤⌊k/2⌋} a_{k−i}b^{k−i} = (a_{k}a_{k−1} ⋯ a_{k−⌊k/2⌋}00 ⋯ 0)_{b}.  (20)

We write

A_{b}(m, q, r) = ∑_{\begin{matrix}n∈P_{b} \\ n ≡ r (mod q) \\ n < b^{k} \end{matrix}} 1 + ∑_{\begin{matrix}n∈P_{b} \\ n ≡ r (mod q) \\ b^{k} ≤ n < a_{k}b^{k} \end{matrix}} 1 + ∑_{\begin{matrix}n∈P_{b} \\ n ≡ r (mod q) \\ a_{k}b^{k} ≤ n < m^{∗} \end{matrix}} 1 + ∑_{\begin{matrix}n∈P_{b} \\ n ≡ r (mod q) \\ m^{∗} ≤ n ≤ m \end{matrix}} 1,  (21)

and divide the calculation into 6 parts.

Part 1 We will show that for integers t ≥ 1,

∑_{\begin{matrix}n∈P_{b} \\ n ≡ r (mod q) \\ b^{t}≤n<b^{t+1} \end{matrix}} 1 = \begin{cases}0, & if q is even, t is odd, and r is odd; \\ \frac{2(b−1)b^{(t−1)/2}}{q} , & if q is even, t is odd, and r is even; \\ \frac{(b−1)^{2}b^{(t/2)−1}}{q} , & if q is even, t is even, and r is odd; \\ \frac{(b−1)(b+1)b^{(t/2)−1}}{q} , & if q is even, t is even, and r is even; \\ \frac{(b−1)b^{⌊t/2⌋}}{q} , & if q is odd. \end{cases}  (22)

Let t ≥ 1 be an integer and n = (c_{t}c_{t−1} ⋯ c_{1}c_{0})_{b} a b-adic palindrome that is counted in the left-hand side of (22). Then we have s_{b}(n) ≡ n ≡ r (mod q). We divide the consideration into four cases according to the parity of q and t.

Case 1.1 q is even and t is odd. We have

2 ∑_{0≤j≤(t−1)/2} c_{t−j} = ∑_{0≤j≤t} c_{j} = s_{b}(n) ≡ r (mod q).  (23)

Since q and the leftmost term in (23) are even, we see that r is even. So if r is odd, then the left-hand side of (22) is equal to 0, which proves the first case of (22). Since r is even, the congruence in (23) is equivalent to

∑_{0≤j≤(t−1)/2} c_{t−j} ≡ r/2 (mod q/2).

Since 1 ≤ c_{t} < b and 0 ≤ c_{t−j} < b for all integers j = 1, 2, …, (t−1)/2, we obtain by Lemma 5 that

∑_{\begin{matrix}n∈P_{b} \\ n ≡ r (mod q) \\ b^{t}≤n<b^{t+1} \end{matrix}} 1 = N_{b} (\frac{t + 1}{2}, q/2, r/2, 1, b) = \frac{b^{(t+1)/2} − b^{(t−1)/2}}{q/2} = \frac{2(b − 1)b^{(t−1)/2}}{q} ,

which proves the second case of (22).

Case 1.2 q and t are odd. This case is similar to Case 1.1, so we skip some details. We also obtain (23), and (23) is equivalent to

∑_{0≤j≤(t−1)/2} c_{t−j} ≡ (\frac{q + 1}{2}) r (mod q).

Therefore the left-hand side of (22) is

N_{b} (\frac{t + 1}{2}, q, (\frac{q + 1}{2}) r, 1, b) = \frac{(b − 1)b^{(t−1)/2}}{q} .

Case 1.3 q and t are even. In this case, we first fix the value of c_{t/2} and then count the number of choices for the remaining c_{j}. We have

c_{t/2} + 2 ∑_{0≤j≤(t/2)−1} c_{t−j} = ∑_{0≤j≤t} c_{j} = s_{n}(n) ≡ r (mod q).  (24)

Then c_{t/2} ≡ r (mod 2) and (24) is equivalent to

∑_{0≤j≤(t/2)−1} c_{t−j} ≡ \frac{r − c_{t/2}}{2} (mod q/2).

Since q is even and b ≡ 1 (mod q), we see that b ≡ 1 (mod 2). By Lemmas 4 and 5, we obtain

∑_{\begin{matrix}n∈P_{b} \\ n ≡ r (mod q) \\ b^{t}≤n<b^{t+1} \end{matrix}} 1 = ∑_{\begin{matrix}0≤c<b \\ c ≡ r (mod 2) \end{matrix}} N_{b} (t/2, q/2, \frac{r − c}{2}, 1, b)

= (\frac{b^{t/2} − b^{(t/2)−1}}{q/2} ) (\frac{b − 1}{2} + [r ≡ 0 (mod 2)])

= \begin{cases}\frac{(b−1)(b+1)b^{(t/2)−1}}{q} , & if r is even; \\ \frac{(b−1)^{2}b^{(t/2)−1}}{q} , & if r is odd, \end{cases}

which proves the third and fourth cases of (22).

Case 1.4 q is odd and t is even. Using a similar method as in Case 1.3, we obtain (24), and (24) is equivalent to

∑_{0≤j≤(t/2)−1} c_{t−j} ≡ (r − c_{t/2}) (\frac{q + 1}{2}) (mod q).

Therefore the left-hand side of (22) is

∑_{0≤c<b} N_{b} (t/2, q, (r − c) (\frac{q + 1}{2}) , 1, b) = \frac{(b − 1)b^{t/2}}{q} .

Combining this and the result in Case 1.2, we obtain the last case of (22).

Part 2 We let S_{1} be the first sum on the right-hand side of (21), and apply (22) to calculate S_{1}. It is straightforward to see that

∑_{\begin{matrix}1≤t≤k−1 \\ t ≡ 0 (mod 2) \end{matrix}} b^{(t/2)−1} = \frac{b^{⌊(k−1)/2⌋} − 1}{b − 1} and ∑_{\begin{matrix}1≤t≤k−1 \\ t ≡ 1 (mod 2) \end{matrix}} b^{(t−1)/2} = \frac{b^{⌊k/2⌋} − 1}{b − 1}.

In addition, we have 1, 2, …, b − 1 are b-adic palindromes, b ≡ 1 (mod q), and S_{1} is equal to

∑_{0≤t≤k−1} ∑_{\begin{matrix}n∈P_{b} \\ n ≡ r (mod q) \\ b^{t}≤n<b^{t+1} \end{matrix}} 1

= ∑_{\begin{matrix}1≤n<b \\ n ≡ r (mod q) \end{matrix}} 1 + ∑_{\begin{matrix}1≤t≤k−1 \\ t ≡ 0 (mod 2) \end{matrix}} ∑_{\begin{matrix}n∈P_{b} \\ n ≡ r (mod q) \\ b^{t}≤n<b^{t+1} \end{matrix}} 1 + ∑_{\begin{matrix}1≤t≤k−1 \\ t ≡ 1 (mod 2) \end{matrix}} ∑_{\begin{matrix}n∈P_{b} \\ n ≡ r (mod q) \\ b^{t}≤n<b^{t+1} \end{matrix}} 1

= ⌊b/q⌋ + ∑_{\begin{matrix}1≤t≤k−1 \\ t ≡ 0 (mod 2) \end{matrix}} ∑_{\begin{matrix}n∈P_{b} \\ n ≡ r (mod q) \\ b^{t}≤n<b^{t+1} \end{matrix}} 1 + ∑_{\begin{matrix}1≤t≤k−1 \\ t ≡ 1 (mod 2) \end{matrix}} ∑_{\begin{matrix}n∈P_{b} \\ n ≡ r (mod q) \\ b^{t}≤n<b^{t+1} \end{matrix}} 1,

where the first sum is obtained by Lemma 4. If q is even and r is odd, then (22) implies

S_{1} = ⌊b/q⌋ + \frac{(b − 1)^{2}}{q} ∑_{\begin{matrix}1≤t≤k−1 \\ t ≡ 0 (mod 2) \end{matrix}} b^{(t/2)−1}

= \frac{b − 1}{q} + (\frac{b − 1}{q}) (b^{⌊(k−1)/2⌋} − 1) = \frac{(b − 1)b^{⌊(k−1)/2⌋}}{q} .  (25)

Similarly, if q and r are even, then

S_{1} = \frac{b − 1}{q} + \frac{(b − 1)(b + 1)}{q} ∑_{\begin{matrix}1≤t≤k−1 \\ t ≡ 0 (mod 2) \end{matrix}} b^{(t/2)−1} + \frac{2(b − 1)}{q} ∑_{\begin{matrix}1≤t≤k−1 \\ t ≡ 1 (mod 2) \end{matrix}} b^{(t−1)/2}

= \frac{b − 1}{q} + (\frac{b + 1}{q}) (b^{⌊(k−1)/2⌋} − 1) + \frac{2 (b^{⌊k/2⌋} − 1)}{q}

= \frac{(b + 1)b^{⌊(k−1)/2⌋} + 2b^{⌊k/2⌋} − 4}{q}.  (26)

If q is odd, then

S_{1} = \frac{b − 1}{q} + \frac{(b − 1)b}{q} ∑_{\begin{matrix}1≤t≤k−1 \\ t ≡ 0 (mod 2) \end{matrix}} b^{(t/2)−1} + \frac{(b − 1)}{q} ∑_{\begin{matrix}1≤t≤k−1 \\ t ≡ 1 (mod 2) \end{matrix}} b^{(t−1)/2}

= \frac{b − 1}{q} + \frac{b^{⌊(k+1)/2⌋} − b}{q} + \frac{b^{⌊k/2⌋} − 1}{q}

= \frac{b^{⌊(k+1)/2⌋} + b^{⌊k/2⌋} − 2}{q}.  (27)

From (25), (26), and (27), we obtain

∑_{\begin{matrix}n∈P_{b} \\ n ≡ r (mod q) \\ 1≤n<b^{k} \end{matrix}} 1 = \begin{cases}\frac{(b−1)b^{⌊(k−1)/2⌋}}{q} , & if q is even and r is odd; \\ \frac{(b+1)b^{⌊(k−1)/2⌋}+2b^{⌊k/2⌋}−4}{q}, & if q and r are even; \\ \frac{b^{⌊(k+1)/2⌋}+b^{⌊k/2⌋}−2}{q}, & if q is odd. \end{cases}  (28)

Part 3 We show that the second sum on the right-hand side of (21) is equal to

\begin{cases}0, & if q is even, k is odd, and r is odd; \\ \frac{2(a_{k}−1)b^{(k−1)/2}−2s_{0}+2}{q} + [r_{0} < s_{0}] − [r = 0], & if q is even, k is odd, and r is even; \\ \frac{(a_{k}−1)(b−1)b^{(k/2)−1}}{q} , & if q is even, k is even, and r is odd; \\ \frac{(a_{k}−1)(b+1)b^{(k/2)−1}−2s_{0}+2}{q} + [r_{0} < s_{0}] − [r = 0], & if q is even, k is even, and r is even; \\ ⌊\frac{a_{k}b^{⌊k/2⌋}}{q} ⌋ − \frac{b^{⌊k/2⌋}−1}{q} + [r_{0} < s_{0}] − [r = 0], & if q is odd. \end{cases} (29)

Let n = (c_{k}c_{k−1} ⋯ c_{1}c_{0})_{b} be a b-adic palindrome satisfying b^{k} ≤ n < a_{k}b^{k} and n ≡ r (mod q). We divide the calculation into four cases.

Case 3.1 q is even and k is odd. We have

2 ∑_{0≤j≤(k−1)/2} c_{k−j} = ∑_{0≤j≤k} c_{j} = s_{b}(n) ≡ r (mod q).  (30)

Since q is even, the second sum on the right-hand side of (21) is zero when r is odd, which proves the first case in (29). Suppose r is even. Then (30) is equivalent to

∑_{0≤j≤(k−1)/2} c_{k−j} ≡ r/2 (mod q/2).

Recall that r_{0} = r/2 mod q/2 and s_{0} = a_{k} mod q/2. In addition, r_{0} = 0 if and only if r = 0 By Lemma 5 (iv), the second sum on the right-hand side of (21) is equal to

N_{b} (\frac{k + 1}{2}, q/2, r/2, 1, a_{k}) = \frac{2(a_{k} − 1) (b^{(k−1)/2} − 1)}{q} + ⌊2a_{k}/q⌋ + [r_{0} < s_{0}] − [r_{0} = 0]

= \frac{2(a_{k} − 1)b^{(k−1)/2} − 2s_{0} + 2}{q} + [r_{0} < s_{0}] − [r = 0],

which proves the second case in (29).

Case 3.2 q and k are odd. Similar to Case 1.2, we have

∑_{0≤j≤(k−1)/2} c_{k−j} ≡ (\frac{q + 1}{2}) r (mod q).

Since b ≡ 1 (mod q), we obtain a_{k}b^{(k−1)/2} ≡ s_{0} (mod q) and so (a_{k}b^{(k−1)/2} − s_{0})/q = ⌊a_{k}b^{⌊k/2⌋}/q⌋. Therefore the second sum on the right-hand side of (21) is equal to

N_{b} (\frac{k + 1}{2}, q, (\frac{q + 1}{2}) r, 1, a_{k})

= \frac{(a_{k} − 1)(b^{(k−1)/2} − 1)}{q} + ⌊a_{k}/q⌋ + [(\frac{q + 1}{2}) r mod q < a_{k} mod q] − [(\frac{q + 1}{2}) r mod q = 0]

= \frac{a_{k}b^{(k−1)/2} − s_{0}}{q} − \frac{b^{(k−1)/2} − 1}{q} + [r_{0} < s_{0}] − [r_{0} = 0]

= ⌊\frac{a_{k}b^{⌊k/2⌋}}{q} ⌋ − \frac{b^{⌊k/2⌋} − 1}{q} + [r_{0} < s_{0}] − [r = 0].

Case 3.3 q and k are even. Similar to Case 1.3, we have c_{k/2} ≡ r (mod 2) and

∑_{0≤j≤(k/2)−1} c_{k−j} ≡ \frac{r − c_{k/2}}{2} (mod q/2).

For 0 ≤ c < b such that c ≡ r (mod 2), define r^{∗}(c) = (r − c)/2 mod q/2. Recall that s_{0} = a_{k} mod q/2. Then by Lemma 5(iv), the second sum on the right-hand side of (21) is equal to

∑_{\begin{matrix}0≤c<b \\ c ≡ r (mod 2) \end{matrix}} N_{b}(k/2, q/2, r^{∗}(c), 1, a_{k})

= ∑_{\begin{matrix}0≤c<b \\ c ≡ r (mod 2) \end{matrix}} (\frac{2(a_{k} − 1)(b^{(k/2)−1} − 1)}{q} + ⌊2a_{k}/q⌋ + [r^{∗}(c) < s_{0}] − [r^{∗}(c) = 0])

= (\frac{2(a_{k} − 1)(b^{(k/2)−1} − 1)}{q} + \frac{2(a_{k} − s_{0})}{q}) (\frac{b − 1}{2} + [r ≡ 0 (mod 2)])

+ ∑_{\begin{matrix}0≤c<b \\ c ≡ r (mod 2) \end{matrix}}([r^{∗}(c) < s_{0}] − [r^{∗}(c) = 0])

= \frac{((a_{k} − 1)b^{(k/2)−1} − s_{0} + 1) (b − 1 + 2[r ≡ 0 (mod 2)])}{q}

+ ∑_{\begin{matrix}0≤c<b \\ c ≡ r (mod 2) \end{matrix}}([r^{∗}(c) < s_{0}] − [r^{∗}(c) = 0]).  (31)

Since b ≡ 1 (mod q), there exists an integer ℓ ≥ 1 such that b = ℓq + 1. In addition, we have b − 1 ≡ 0 (mod 2), and so if r is even, then r^{∗}(b − 1) ≡ (r − (b − 1))/2 ≡ r/2 (mod q/2) and thus r^{∗}(b − 1) = r_{0} and [r_{0} = 0] = [r = 0]. Then the last sum in (31) is

[r ≡ 0 (mod 2)] ([r_{0} < s_{0}] − [r = 0]) + ∑_{1≤j≤ℓ} ∑_{\begin{matrix}(j−1)q≤c<jq \\ c ≡ r (mod 2) \end{matrix}}([r^{∗}(c) < s_{0}] − [r^{∗}(c) = 0]). (32)

We see that {(r − c)/2 | c ≡ r (mod 2) and (j − 1)q ≤ c < jq} is a complete residue system modulo q/2 for any j = 1, 2, …, ℓ. So

∑_{1≤j≤ℓ} ∑_{\begin{matrix}(j−1)q≤c<jq \\ c ≡ r (mod 2) \end{matrix}}([r^{∗}(c) < s_{0}] − [r^{∗} = 0]) = ∑_{1≤j≤ℓ}(s_{0} − 1) = \frac{b − 1}{q}(s_{0} − 1).  (33)

From (31), (32), and (33), we obtain that the second sum on the right-hand side of (21) is

\frac{(a_{k} − 1)(b − 1 + 2[r ≡ 0 (mod 2)])b^{(k/2)−1} − 2(s_{0} − 1)[r ≡ 0 (mod 2)]}{q}

+ [r ≡ 0 (mod 2)] ([r_{0} < s_{0}] − [r = 0])

= \begin{cases}\frac{(a_{k}−1)(b−1)b^{(k/2)−1}}{q} , & if r is odd; \\ \frac{(a_{k}−1)(b+1)b^{(k/2)−1}−2(s_{0}−1)}{q} + [r_{0} < s_{0}] − [r = 0], & if r is even, \end{cases}

which proves the third and fourth cases in (29).

Case 3.4 q is odd and k is even. This case is similar to Case 3.3. We have

∑_{0≤j≤(k/2)−1} c_{k−j} ≡ (r − c_{k/2}) (\frac{q + 1}{2}) (mod q).

For 0 ≤ c < b, let r^{∗}(c) = ((r − c)(q + 1)/2) mod q. Since gcd((q + 1)/2, q) = 1 and

{c | (j − 1)q ≤ c < jq} is a complete residue system modulo q,

the set {r^{∗}(c) | (j − 1)q ≤ c < jq} is also a complete residue system modulo q for any j = 1, 2, …, (b − 1)/q. In addition,

r^{∗}(b − 1) ≡ \frac{(r − (b − 1))(q + 1)}{2} ≡ \frac{(q + 1)r}{2} ≡ r_{0} (mod q),

[r_{0} = 0] = [r = 0], and (a_{k}b^{k/2} − s_{0})/q = ⌊a_{k}b^{⌊k/2⌋}/q⌋. Therefore

∑_{\begin{matrix}n∈P_{b} \\ n ≡ r (mod q) \\ b^{k} ≤ n < a_{k}b^{k} \end{matrix}} 1 = ∑_{0≤c<b} N_{b} (k/2, q, r^{∗}(c), 1, a_{k})

= ∑_{0≤c<b} (\frac{(a_{k} − 1)b^{(k/2)−1} − s_{0} + 1}{q} + [r^{∗}(c) < s_{0}] − [r^{∗}(c) = 0])

= \frac{(a_{k} − 1)b^{k/2} − (s_{0} − 1)b}{q} + ∑_{0≤c<b} ([r^{∗}(c) < s_{0}] − [r^{∗}(c) = 0])

= \frac{(a_{k} − 1)b^{k/2} − (s_{0} − 1)b}{q} + \frac{(b − 1)}{q}(s_{0} − 1) + [r_{0} < s_{0}] − [r = 0]

= \frac{a_{k}b^{k/2} − s_{0}}{q} − \frac{b^{k/2} − 1}{q} − \frac{(b − 1)}{q}(s_{0} − 1) + \frac{(b − 1)}{q}(s_{0} − 1) + [r_{0} < s_{0}] − [r = 0]

= ⌊\frac{a_{k}b^{⌊k/2⌋}}{q} ⌋ − \frac{b^{⌊k/2⌋} − 1}{q} + [r_{0} < s_{0}] − [r = 0].

Combining Case 3.2 and Case 3.4, we obtain the last case in (29). Therefore the proof of (29) is complete.

Part 4 For each j ∈ {0, 1, …, ⌊k/2⌋}, let

m_{j} = ∑_{0≤i≤j} a_{k−i}b^{k−i} = (a_{k}a_{k−1} ⋯ a_{k−j}00 ⋯ 0)_{b}.  (34)

For 1 ≤ j ≤ ⌊k/2⌋, we will show that

∑_{\begin{matrix}n∈P_{b} \\ n ≡ r (mod q) \\ m_{j−1}≤n<m_{j} \end{matrix}} 1 = \begin{cases}0, & if q is even, k is odd, and r is odd; \\ \frac{2a_{k−j}b^{((k−1)/2)−j}−2s_{j}}{q} + [r_{j} < s_{j}], & if q is even, k is odd, and r is even; \\ \frac{a_{k−j}(b−1)b^{(k/2)−j−1}}{q} , & if q is even, k is even, j < k/2, and r is odd; \\ \frac{a_{k−j}(b+1)b^{(k/2)−j−1}−2s_{j}}{q} + [r_{j} < s_{j}] , & if q is even, k is even, j < k/2, and r is even; \\ ⌊\frac{a_{k/2}}{q} ⌋ + [r_{k/2} < s_{k/2}] , & if q is even, k is even, and j = k/2; \\ ⌊\frac{a_{k−j}b^{⌊k/2⌋−j}}{q} ⌋ + [r_{j} < s_{j}], & if q is odd. \end{cases}

(35)

Let 1 ≤ j ≤ ⌊k/2⌋, A the sum on the left-hand side of (35), and n = (c_{k}c_{k−1} ⋯ c_{1}c_{0})_{b} a b-adic palindrome which is counted in the left-hand side of (35). Since m_{j−1} ≤ n < m_{j},

m_{j−1} = (a_{k}a_{k−1} ⋯ a_{k−(j−1)}00 ⋯ 0)_{b}, and m_{j} = (a_{k}a_{k−1} ⋯ a_{k−j}00 ⋯ 0)_{b},

the following properties hold:

1. c_{i} = c_{k−i} for all i = 0, 1, 2, …, k.

2. c_{k−i} = a_{k−i} for all i = 0, 1, 2, …, j − 1.

3. 0 ≤ c_{k−j} < a_{k−j}.

4. 0 ≤ c_{k−i} < b for all i = j + 1, j + 2, …, ⌊k/2⌋.

We see that there are only one choice for each c_{0}, c_{1}, …, c_{j−1}, c_{k−j+1}, c_{k−j+2}, …, c_{k} and A depends on the choices of c_{i} for j ≤ i ≤ ⌊k/2⌋. We divide the calculation into two cases.

Case 4.1 q is even and k is odd. We have

2 ∑_{0≤i≤(k−1)/2} c_{k−i} = ∑_{0≤i≤k} c_{i} = s_{b}(n) ≡ r (mod q).  (36)

Then (36) is impossible when r is odd, so A = 0, which proves the first case in (35). Suppose r is even. From the above properties and the definition of r_{j}, we obtain that (36) is equivalent to

∑_{j≤i≤(k−1)/2} c_{k−i} ≡ r/2 − ∑_{0≤i≤j−1} c_{k−i} ≡ r/2 − ∑_{0≤i≤j−1} a_{k−i} ≡ r_{j} (mod q/2),

and A is equal to

N_{b} (\frac{k − 1}{2} − j + 1, q/2, r_{j}, 0, a_{k−j})

= \frac{2a_{k−j} (b^{((k−1)/2)−j} − 1)}{q} + ⌊\frac{2a_{k−j}}{q} ⌋ + [r_{j} mod q/2 < a_{k−j} mod q/2]

= \frac{2a_{k−j} (b^{((k−1)/2)−j} − 1)}{q} + \frac{2(a_{k−j} − s_{j})}{q} + [r_{j} < s_{j}]

= \frac{2a_{k−j}b^{((k−1)/2)−j} − 2s_{j}}{q} + [r_{j} < s_{j}],

which proves the second case in (35).

Case 4.2 q and k are odd. Similar to Case 4.1, we have

∑_{j≤i≤(k−1)/2} c_{k−i} ≡ (\frac{q + 1}{2}) r − ∑_{0≤i≤j−1} a_{k−i} ≡ r_{j} (mod q).

In addition, a_{k−j}b^{(k−1)/2−j} ≡ s_{j} (mod q). Therefore

A = N_{b} (\frac{k − 1}{2} − j + 1, q, r_{j}, 0, a_{k−j})

= \frac{a_{k−j}b^{((k−1)/2)−j} − s_{j}}{q} + [r_{j} < s_{j}] = ⌊\frac{a_{k−j}b^{⌊k/2⌋−j}}{q} ⌋ + [r_{j} < s_{j}].

Case 4.3 q and k are even. Using the same method of calculation, we have c_{k/2} ≡ r (mod 2) and

∑_{0≤i≤(k/2)−1} c_{k−i} ≡ \frac{r − c_{k/2}}{2} (mod q/2).

Case 4.3.1 j < k/2. We have

∑_{j≤i≤(k/2)−1} c_{k−i} ≡ \frac{r − c_{k/2}}{2} − ∑_{0≤i≤j−1} c_{k−i} ≡ \frac{r − c_{k/2}}{2} − ∑_{0≤i≤j−1} a_{k−i} (mod q/2).

For 0 ≤ c < b and c ≡ r (mod 2), define r_{j}^{∗}(c) = ((r − c)/2 − ∑_{0≤i≤j−1} a_{k−i}) mod q/2.

Then A is equal to

∑_{\begin{matrix}0≤c<b \\ c ≡ r (mod 2) \end{matrix}} N_{b} ((k/2) − j, q/2, r_{j}^{∗}(c), 0, a_{k−j})

= ∑_{\begin{matrix}0≤c<b \\ c ≡ r (mod 2) \end{matrix}} (\frac{2a_{k−j} (b^{(k/2)−j−1} − 1)}{q} + ⌊\frac{2a_{k−j}}{q} ⌋ + [r_{j}^{∗}(c) < s_{j}])

= (\frac{2a_{k−j}b^{(k/2)−j−1} − 2s_{j}}{q} ) (\frac{b − 1}{2} + [r ≡ 0 (mod 2)]) + ∑_{\begin{matrix}0≤c<b \\ c ≡ r (mod 2) \end{matrix}}[r_{j}^{∗}(c) < s_{j}]. (37)

Similar to Case 3.3, we write b = ℓq + 1 for some ℓ ∈ ℤ, and obtain that

{r_{j}^{∗}(c) | c ≡ r (mod 2) and (i − 1)q ≤ c < iq}

is a complete residue system modulo q/2 for any i = 1, 2, …, ℓ, and if r is even, then

r_{j}^{∗}(b − 1) ≡ \frac{r − (b − 1)}{2} − ∑_{0≤i≤j−1} a_{k−i} ≡ r/2 − ∑_{0≤i≤j−1} a_{k−i} ≡ r_{j} (mod q/2).

Therefore the last sum in (37) is

[r ≡ 0 (mod 2)][r_{j} < s_{j}] + ∑_{1≤i≤ℓ} ∑_{\begin{matrix}(i−1)q≤c<iq \\ c ≡ r (mod 2) \end{matrix}}[r_{j}^{∗}(c) < s_{j}]

= [r ≡ 0 (mod 2)][r_{j} < s_{j}] + ∑_{1≤i≤ℓ} s_{j}

= [r ≡ 0 (mod 2)][r_{j} < s_{j}] + \frac{b − 1}{q}s_{j}.  (38)

From (37) and (38), we have

A = \frac{a_{k−j}(b − 1)b^{(k/2)−j−1}}{q} + [r ≡ 0 (mod 2)] (\frac{2a_{k−j}b^{(k/2)−j−1} − 2s_{j}}{q} + [r_{j} < s_{j}])

= \begin{cases}\frac{a_{k−j}(b−1)b^{(k/2)−j−1}}{q} , & if r ≡ 1 (mod 2); \\ \frac{a_{k−j}(b+1)b^{(k/2)−j−1}−2s_{j}}{q} + [r_{j} < s_{j}] , & if r ≡ 0 (mod 2), \end{cases}

which proves the third and fourth case in (35).

Case 4.3.2 j = k/2. Then A depends only on the choices of c_{k/2} and

c_{k/2} ≡ r − 2 ∑_{0≤i≤(k/2)−1} c_{k−i} ≡ r − 2 ∑_{0≤i≤(k/2)−1} a_{k−i} ≡ r_{k/2} (mod q).

By Lemma 4, we obtain that

A = ∑_{\begin{matrix}0≤c<a_{k/2} \\ c ≡ r_{k/2} (mod q) \end{matrix}} 1 = ⌊\frac{a_{k/2}}{q} ⌋ + [r_{k/2} < s_{k/2}],

which proves the fifth case in (35).

Case 4.4 q is odd and k is even. There is a similarity between Case 4.3 and this case, so we skip some details.

Case 4.4.1 j < k/2. For 0 ≤ c < b, define r_{j}^{∗}(c) = ((r − c)(q + 1)/2 − ∑_{0≤i≤j−1} a_{k−i}) mod q. We see that {r_{j}^{∗}(c) | (i − 1)q ≤ c < iq} is a complete residue system modulo q for any i = 1, 2, …, (b − 1)/q. In addition, r_{j}^{∗}(b − 1) = r_{j} and a_{k−j}b^{k/2−j} ≡ s_{j} (mod q). We have

∑_{j≤i≤(k/2)−1} c_{k−i} ≡ (r − c_{k/2}) (\frac{q + 1}{2}) − ∑_{0≤i≤j−1} a_{k−i} (mod q), and

A = ∑_{0≤c<b} N_{b} ((k/2) − j, q, r_{j}^{∗}(c), 0, a_{k−j})

= ∑_{0≤c<b} (\frac{a_{k−j}b^{(k/2)−j−1} − s_{j}}{q} + [r_{j}^{∗}(c) < s_{j}])

= \frac{a_{k−j}b^{(k/2)−j} − s_{j}b}{q} + ∑_{0≤c<b}[r_{j}^{∗}(c) < s_{j}]

= \frac{a_{k−j}b^{(k/2)−j} − s_{j}}{q} − (\frac{b − 1}{q}) s_{j} + (\frac{b − 1}{q}) s_{j} + [r_{j} < s_{j}]

= ⌊\frac{a_{k−j}b^{⌊k/2⌋−j}}{q} ⌋ + [r_{j} < s_{j}].

Case 4.4.2 j = k/2. Then A depends only on the choices of c_{k/2} and

c_{k/2} ≡ r − 2 ∑_{0≤i≤(k/2)−1} a_{k−i} ≡ r_{k/2} (mod q).

By Lemma 4, we obtain

A = ∑_{\begin{matrix}0≤c<a_{k/2} \\ c ≡ r_{k/2} (mod q) \end{matrix}} 1 = ⌊\frac{a_{k/2}}{q} ⌋ + [r_{k/2} < s_{k/2}] .

Combining the results in Case 4.2 and in this case, we obtain the last case in (35). Therefore the verification of (35) is complete.

Part 5 In this part, we compute the third sum on the right-hand side of (21). Recall the definitions of m^{∗} and m_{j} given in (20) and (34), and the definitions of m_{1}^{∗}, m_{2}^{∗}, and m_{3}^{∗} given in the statement of this theorem. We see that the third sum on the right-hand side of (21) is

∑_{\begin{matrix}n∈P_{b} \\ n ≡ r (mod q) \\ a_{k}b^{k}≤n<m^{∗} \end{matrix}} 1 = ∑_{1≤j≤⌊k/2⌋} ∑_{\begin{matrix}n∈P_{b} \\ n ≡ r (mod q) \\ m_{j−1}≤n<m_{j} \end{matrix}} 1.  (39)

From (35) and (39), we obtain that the third sum on the right-hand side of (21) is equal to

0,  if q is even, k is odd,

and r is odd;

m_{1}^{∗} − \frac{2a_{k}b^{(k−1)/2}−2s_{0}}{q} − [r_{0} < s_{0}],  if q is even, k is odd,

and r is even;

m_{2}^{∗} − \frac{a_{k}(b−1)b^{(k/2)−1}}{q} + ⌊\frac{a_{k/2}}{q} ⌋ + [r_{k/2} < s_{k/2}] ,  if q is even, k is even,

and r is odd;

m_{3}^{∗} − \frac{a_{k}(b+1)b^{(k/2)−1}−2s_{0}}{q} − [r_{0} < s_{0}] + ⌊\frac{a_{k/2}}{q} ⌋ + [r_{k/2} < s_{k/2}] , if q is even, k is even,

and r is even;

∑_{1≤j≤⌊k/2⌋} (⌊\frac{a_{k−j}b^{⌊k/2⌋−j}}{q} ⌋ + [r_{j} < s_{j}]) ,  if q is odd.

(40)

Part 6 Let L be the last sum in (21). We will calculate L and A_{q}(m, q, r). The only possible b-adic palindrome n lying in the interval [m^{∗}, m] is n = C_{b}(m). Therefore

L = [m ≥ C_{b}(m)][C_{b}(m) ≡ r (mod q)].

If k is odd, then C_{b}(m) ≡ r (mod q) if and only if

2 ∑_{0≤j≤(k−1)/2} a_{k−j} = s_{b} (C_{b}(m)) ≡ r (mod q).  (41)

Similarly, if k is even, then C_{b}(m) ≡ r (mod q) if and only if

2 ∑_{0≤j≤(k/2)−1} a_{k−j} + a_{k/2} = s_{b} (C_{b}(m)) ≡ r (mod q).  (42)

If k is even, then (42) is equivalent to r_{⌊k/2⌋} = s_{⌊k/2⌋}. If k is odd, q is even, and r is odd, then (41) is not possible, and so L = 0. In the remaining cases, the congruence (41) is equivalent to r_{⌊k/2⌋} = s_{⌊k/2⌋}. Therefore

L = \begin{cases}0, & if k is odd, q is even, and r is odd; \\ δ(m), & otherwise. \end{cases}  (43)

Therefore the desired formula for A_{b}(m, q, r) can be obtained from (21), (28), (29), (40), and (43). This completes the proof.

The formulas presented in Theorems 7 and 9 may look complicated. However, by examining certain special cases, the formulas are of a simpler form as shown in the corollary.

Corollary 11. Let b ≥ 2, k, q ≥ 1, and 0 ≤ r < q be integers. Then the following statements hold.

(i) Assume that b ≡ 0 (mod q). Then

A_{b} (b^{k}, q, r) = ((b/q) − [r = 0]) (\frac{b^{⌈k/2⌉} + b^{⌊k/2⌋} − 2}{b − 1})

(ii) Assume that b ≡ 1 (mod q). Then

A_{b} (b^{k}, q, r) = \begin{cases}\frac{b^{⌈k/2⌉}+b^{⌊k/2⌋}−2}{q}, & if q is odd; \\ \frac{(b−1)b^{⌊(k−1)/2⌋}}{q} , & if q is even and r is odd; \\ \frac{(b+1)b^{⌊(k−1)/2⌋}+2b^{⌊k/2⌋}−4}{q}, & if q and r are even. \end{cases}

Proof. We see that C_{b}(b^{k}) = b^{k} + 1 > b^{k}, which implies that [b^{k} ≥ C_{b}(b^{k})] = 0. In addition, if r > 0, then ⌈(1 − r)/q⌉ = 0. Then (i) follows from Theorem 7. For (ii), let m = b^{k} = (100 ⋯ 0)_{b} and let m_{1}^{∗}, m_{2}^{∗}, m_{3}^{∗}, r_{j}, s_{j} for each 0 ≤ j ≤ ⌊k/2⌋ be defined as in Theorem 9. Then for 0 ≤ j ≤ ⌊k/2⌋, we have

s_{j} = \begin{cases}1, & if j = 0; \\ 0, & if j ≠ 0, \end{cases}

[r_{j} < s_{j}] = \begin{cases}[r = 0], & if j = 0; \\ 0, & if j ≠ 0, \end{cases}

m_{1}^{∗} = \frac{2b^{(k−1)/2} − 2}{q} + [r = 0], m_{2}^{∗} = \frac{2b^{(k−1)/2} − 2}{q},

m_{3}^{∗} = \frac{(b + 1)b^{(k/2)−1} − 2}{q}, and [m ≥ C_{b}(m)] = 0.

From the above observation and Theorem 9, we obtain (ii).

The next corollary gives a supplementary result to Col’s theorems [8]. Recall that if we write f(b) = g(b) + O^{∗}(h(b)), then it means that f(b) = g(b) + O(h(b)) and the implied constant can be taken to be 1.

Corollary 12. Let b ≥ 2, q ≥ 1, and 0 ≤ r < q be integers. Assume that q is odd and b ≡ 1 (mod q). Then uniformly for m ≥ 1, we have

A_{b}(m, q, r) = \frac{1}{q}A_{b}(m) + O^{∗} (\frac{log m}{2 log b} + 2) .

Proof. If q = 1, then A_{b}(m, q, r) = A_{b}(m)/q and the result follows immediately. So assume that q ≥ 2. Let m = (a_{k}a_{k−1} ⋯ a_{1}a_{0})_{b}. By Corollary 8 and Theorem 9, we obtain

\frac{1}{q}A_{b}(m) = \frac{b^{⌊(k+1)/2⌋}}{q} + ∑_{0≤i≤⌊\frac{k}{2}⌋} \frac{a_{k−i}b^{⌊k/2⌋−i}}{q} + \frac{[m ≥ C_{b}(m)] − 2}{q} and

A_{b}(m, q, r) = \frac{b^{⌊(k+1)/2⌋} − 1}{q} + ∑_{0≤j≤⌊\frac{k}{2}⌋} (⌊\frac{a_{k−j}b^{⌊k/2⌋−j}}{q} ⌋ + [r_{j} < s_{j}]) − [r = 0] + δ(m),

where r_{0}, …, r_{⌊k/2⌋}, s_{0}, …, s_{⌊k/2⌋}, δ(m) are defined as in Theorem 9. In addition, we also have k = ⌊(log m)/(log b)⌋ and 0 ≤ x − ⌊x⌋ < 1 for all x ∈ ℝ. If δ(m) = 1, then [m ≥ C_{b}(m)] = 1. If δ(m) = 0, then 0 ≤ [m ≥ C_{b}(m)] ≤ 1. Therefore

A_{b}(m, q, r) − \frac{1}{q}A_{b}(m) ≤ −(1/q) + ((k/2) + 1) + 1 + 1/q = (k/2) + 2.

It is also easy to see that

A_{b}(m, q, r) − \frac{1}{q}A_{b}(m) ≥ −(1/q) − ((k/2) + 1) − 1 + 1/q = −(k/2) − 2.

Hence |A_{b}(m, q, r) − A_{b}(m)/q| ≤ k/2 + 2 ≤ (log m)/(2 log b) + 2, as required.

4 Conclusion and open questions

We obtain exact formulas for the number of b-adic palindromes not exceeding a positive integer m that lie in an arithmetic progression r mod q when b ≡ 0, 1 (mod q). By modifying Lemmas, we strongly believe that an analogous formula for the case b ≡ −1 (mod q) can be obtained, but we have not proceeded to a calculation yet to avoid making this article too lengthy. We also derive an asymptotic formula for the number of b-adic palindrome that are at most m and are congruent to r modulo q when q is odd and b ≡ 1 (mod q) that gives an equidistribution result in residue classes modulo q extending Col’s result [8], which is under the different condition gcd(b(b^{2} − 1), q) = 1. We currently do not have sufficiently satisfactory or interesting results in the other cases. This leads us to some open questions.

Problem 13. What can we say about the distribution of b-adic palindromes in residue classes modulo q when b ≢ −1, 0, 1 (mod q) and gcd(b(b^{2} − 1), q) > 1? Are they uniformly distributed?

Problem 14. Is there any nontrivial case for b and q that b-adic palindromes are not asymptotically equidistributed in residue classes modulo q? A trivial case is, for example, when r = 0, b = 10, and q is a power of 10 where A_{b}(m, q, r) = A_{10}(m, q, r) = 0 for all m.

Problem 15. What are the necessary and sufficient conditions on b and q for an (asymptotic) equidistributed result?

5 Acknowledgments

We are grateful to the referee for his or her suggestions that improve the quality and presentation of this paper. Prapanpong Pongsriiam’s research project is supported jointly by the Faculty of Science Silpakorn University and the National Research Council of Thailand (NRCT), grant number NRCT5-RSA63021-02. He was also supported by the Tosio Kato Fellowship given by the Mathematical Society of Japan during his visit at Nagoya University in July 2022 to July 2023. This work was started when he was in Japan and finished when he came back to Thailand. He is thankful to Professor Kohji Matsumoto for being his host professor and finding a very convenient and comfortable accommodation and office for him during his visit at Nagoya University.

References

[1] W. D. Banks, Every natural number is the sum of forty-nine palindromes, Integers 16 (2016), Paper No. A3.

[2] W. D. Banks, D. N. Hart, and M. Sakata, Almost all palindromes are composite, Math. Res. Lett. 11 (2004), 853–868.

[3] W. D. Banks and I. Shparlinski, Prime divisors of palindromes, Period. Math. Hungar. 51 (2005), 1–10.

[4] B. Bas̆ić, On d-digit palindromes in different bases: the number of bases is unbounded, Int. J. Number Theory 8 (2012), 1387–1390.

[5] B. Bas̆ić, On “very palindromic”sequences, J. Korean Math. Soc. 52 (2015), 765–780.

[6] J. Cilleruelo, F. Luca, and L. Baxter, Every positive integer is a sum of three palindromes, Math. Comp. 87 (2018), 3023–3055.

[7] J. Cilleruelo, F. Luca, and R. Tesoro, Palindromes in linear recurrence sequences, Monatsh. Math. 171 (2013), 433–442.

[8] S. Col, Palindromes dans les progressions arithmétiques, Acta Arith. 137 (2009), 1–41.

[9] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics: A Foundation for Computer Science, Second Edition, Addison–Wesley, 1994.

[10] E. H. Goins, Palindromes in different bases: A conjecture of J. Ernest Wilkins, Integers 9 (2009), 725–734.

[11] M. Harminc and R. Soták, Palindromic numbers in arithmetic progressions, Fibonacci Quart. 36 (1998), 259–262.

[12] I. Korec, Palindromic squares for various number system bases, Math. Slovaca 41 (1991), 261–276.

[13] F. Luca and A. Togbé, On binary palindromes of the form 10^{n} ± 1, C. R. Math. Acad. Sci. Paris 346 (2008), 487–489.

[14] D. Pálvölgyi, Is there an arbitrarily long arithmetic progression whose members are palindromes? A question on MathOverflow. Available at bit.ly/3W44hmT.

[15] P. Phunphayap and P. Pongsriiam, Reciprocal sum of palindromes, J. Integer Sequences 22 (2019), Article 19.8.6.

[16] P. Pongsriiam, Analytic Number Theory for Beginners, Student Mathematical Library, Vol. 103, American Mathematical Society, 2023.

[17] P. Pongsriiam, Longest arithmetic progressions of palindromes, J. Number Theory 222 (2021), 362–375.

[18] P. Pongsriiam and K. Subwattanachai, Exact formulas for the number of palindromes up to a given positive integer, Int. J. Math. Comput. Sci. 14 (2019), 27–46.

[19] A. Rajasekaran, J. Shallit, and T. Smith, Sums of palindromes: an approach via automata, in 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), Article no. 54, pp. 54:1–54:12.

[20] A. J. Di Scala and M. Sombra, Intrinsic palindromes, Fibonacci Quart. 42 (2004), 76–81.

[21] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, 2024, https://oeis.

    org.

[22] T. Tao, A comment on MathOverflow. Available at bit.ly/3W44hmT.

[23] Vepir, Which number base contains the most palindromic numbers?, Mathematics Stack Exchange. Available at bit.ly/3HCcLNR.

2020 Mathematics Subject Classification: Primary 11A63; Secondary 05A15. Keywords: palindrome, arithmetic progression, palindromic number, digit, b-adic expansion, enumeration.

(Concerned with sequences \underline{A002113} and \underline{A006995}.)

Received July 1 2023; revised versions received April 2 2024; April 4 2024. Published in Journal of Integer Sequences, April 13 2024.

Return to Journal of Integer Sequences home page.