Extremal orders and races between palindromes in different bases

1.   Introduction

Let $b \geq 2$ and $n\geq 1$ 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}\cdots a_0)_b$ with $a_k\neq 0$ has the symmetric property $a_{k-i} = a_i$ for $0\leq i \leq k$. 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} \cdots a_0)_b$, then it means that $n = \sum_{i = 0}^k a_i b^{i}$, $a_k \neq 0$, and $0 \leq a_i < b$ for all $i = 0, 1, \ldots, k$. So, for example, $9 = (1001)_2 = (100)_3$ is a palindrome in bases 2 and 10 but not in base 3.

For a long time ago, palindromes were considered only as a part of recreational mathematics, but in recent years, there has been an increasing interest in the importance of palindromes in mathematics ^{[1,2,3,16,25]}, theoretical computer science ^[4,15,17,18], and theoretical physics ^[5,13,21]. For example, in 2016, Banks ^[6] showed that every positive integer can be written as the sum of at most 49 palindromes in base $10$. Two years later Cilleruelo, Luca, and Baxter ^[11] improved it by showing that if $b \geq 5$ is fixed, then every positive integer is the sum of at most three $b$-adic palindromes. Then Rajasekaran, Shallit, and Smith ^[31] completed the study by proving that the theorem of Cilleruelo, Luca, and Baxter ^[11] also holds when $b\in \{3, 4\}$, and if $b = 2$, then we need four summands to write every positive integer as a sum of $b$-adic palindromes. Nevertheless, we still have many other interesting open problems concerning palindromes. In particular, on Mathematics Stack Exchange, Vepir asked: which number base contains the most palindromic numbers?

Pongsriiam and Subwattanachai ^[30] started the investigation by deriving an exact formula for the number of $b$-adic palindromes not exceeding $n$, denoted by $A_b(n)$, but the formula is difficult to analyze, and so it does not give an answer to Vepir's question. Then Phunphayap and Pongsriiam ^[28] calculated the reciprocal sum of all $b$-adic palindromes implying that if $b > b_1$ and if we use the logarithmic measure, then there are more $b$-adic palindromes than $b_{1}$-adic palindromes. Nevertheless, this does not answer Vepir's question according to the counting measure.

In this article, we obtain extremal orders of $A_b (n)$ and show that $A_{b} (n) - A_{b_{1}} (n)$ has infinitely many sign changes. We also obtain other related results and use them to solve Vepir's problem.

For more information on the palindromes, we refer the reader to Banks, Hart, and Sakata ^[7] and Banks and Shparlinski ^[8] for some multiplicative properties of palindromes, Bašić ^[9,10], Di Scala and Sombra ^[14], Goins ^[19], Luca and Togbé ^[26] for the study of palindromes in different bases, Cilleruelo, Luca, and Tesoro ^[12] for palindromes in linear recurrence sequences, Harminc and Soták ^[20] for $b$-adic palindromes in arithmetic progressions, Korec ^[23] for nonpalindromic numbers having palindromic squares, and Pongsriiam ^[29] for the longest arithmetic progressions of palindromes.

2.   Preliminaries and lemmas

In this section, we provide some definitions and lemmas which are needed in the proof of the main theorems. Recall that for a real number $x$, $\lfloor x \rfloor$ is the largest integer less than or equal to $x$, $\lceil x \rceil$ is the smallest integer greater than or equal to $x$, and $\{ x \}$ is the fractional part of $x$ given by $\{ x \} = x - \lfloor x \rfloor$. Furthermore, for a mathematical statement $P$, the Iverson notation $[P]$ is defined by

In the proof of our main results, we often use Pongsriiam and Subwattanachai's formula ^[30]. So it is convenient to define $C_b (n)$ as follows.

Definition 1. Let $b \geq 2$ and $n \geq 1$ be integers, and $n = (a_k a_{k - 1} \cdots a_{1} a_0)_b$. Define $C_b(n) = (c_k c_{k - 1} \cdots c_1 c_0)_b$ to be the $b$-adic palindrome satisfying $c_i = a_i$ for $k - \lfloor k/2 \rfloor \leq i \leq k$. In other words, $C_b (n)$ is the $b$-adic palindrome having $k+1$ digits, the first half of which are the same as those of $n$ in its $b$-adic expansion, that is, $C_b(n) = (a_k a_{k-1} \cdots a_{k - \left\lfloor \frac{k}{2} \right\rfloor} \cdots a_{k-1} a_k)_b$.

Example 2. If $m = (247853)_9$ and $n = (1327021)_8$, then $C_9 (m) = (247742)_9$ and $C_8 (n) = (1327231)_8$.

Note that our definition of $C_b (n)$ is slightly different from that in Pongsriiam and Subwattanachai's formula ^[30]. In addition, while we focus only on positive integers, they ^[30] also count zero. After a slight modification, their formula is as follows.

Lemma 3 (Pongsriiam and Subwattanachai ^[30]). Let $b \geq 2$ and $n \geq 1$ be integers, and $n = (a_k a_{k-1} \cdots a_1 a_0)_b$. Then the number of $b$-adic palindromes less than or equal to $n$ is given by

where $[n \geq C_{b} (n)]$ is the Iverson notation.

The next lemma gives an upper bound for $A_b (n)$. By Theorem 9, we will see later that the inequality in Lemma 4 is sharp.

Lemma 4. Let $b \geq 2$ and $n \geq 1$ be integers. Then

Proof. We write $n = (a_k a_{k-1} \cdots a_1 a_0)_b$ and let

We see that $y \leq n$, $y = b^k z$, and $1 \leq z \leq (b-1) \sum_{i = 0}^\infty b^{-i} = b$. By Lemma 3, we obtain

Therefore,

We divide the consideration into two cases according to the parity of $k$.

Case 1. $k$ is even. Then

Since the function $x \mapsto \sqrt{x} + \frac{1}{\sqrt{x}}$ is increasing on $[1, \infty]$ and $1\leq z \leq b$, we have

Case 2. $k$ is odd. This case is similar to Case 1. We have

Since $1 \leq z \leq b$, we obtain $1 \leq b/z \leq b$ and therefore

In any case, we obtain the desired result.

Recall that a sequence $(x_n)_{n \geq 1}$ of real numbers is said to be uniformly distributed modulo 1 if for any $0 \leq a < b \leq 1$,

A well-known criterion for uniform distribution modulo 1 is as follows [24,page 7].

Lemma 5. (Weyl's Criterion) The sequence $(x_n)_{n \geq 1}$ is uniformly distributed modulo 1 if and only if

Lemma 6. Let $(x_n)_{n\geq 1}$ be an arithmetic progression of real numbers, $d$ the common difference, $d \in \mathbb{Z}\setminus \{0\}$, and $\alpha \in \mathbb{R}$ an irrational number. Then $(\alpha x_n)_{n\geq 1}$ is uniformly distributed modulo 1.

Proof. Since $\alpha$ is irrational, $d\neq 0$, and $d \in \mathbb{Z}$, we have $\left| e^{2\pi i h \alpha d} - 1 \right| \neq 0$ for all integers $h \neq 0$. Recall that $x_n = x_1 + (n - 1)d$ for all $n \geq 1$. So if $h$ is a nonzero integer, then

which converges to 0 as $N \rightarrow \infty$. By Weyl's criterion, the desired result is verified.

The next result is an important tool for obtaining Theorem 11.

Lemma 7. Let $(x_n)_{n\geq 1}$, $d \geq 1$, and $\alpha$ satisfy the same assumption as in Lemma 6, $x_n\in \mathbb Z$ for every $n$, and let $c \in (0, 1)$. Then there are infinitely many integers $k \geq 1$ such that

Proof. Suppose for a contradiction that there is only a finite number of integers $k \geq 1$ such that $x_k$ satisfies (2.1). Let $k$ be the largest such an integer if it exists and let $k = 1$ otherwise. Since $d \geq 1$, we see that $(x_n)_{n \geq 1}$ is strictly increasing, and so if $n > k$, then $x_n$ does not satisfy (2.1). We will get a contradiction by constructing an integer $x = x_n$ satisfying (2.1) and $n > k$. By Lemma 6, $(\alpha x_{n})_{n\geq 1}$ is uniformly distributed modulo 1. From this point on, we apply the above fact repeatedly without reference. Let $k_1, k_2, \ldots, k_{d}$ be integers satisfying

Then $\left\lfloor \alpha x_{k_i} \right\rfloor \equiv 1 \ (\mathrm{mod}\ {2})$ for all $i = 1, 2, \ldots, d$. We divide the consideration into two cases.

Case 1. $d$ is even. Let $k_{d+1}$ be an integer such that

Case 1.1 $\left\lfloor \alpha x_{k_{d+1}} \right\rfloor \equiv 1 \ (\mathrm{mod}\ {2})$. We see that

This implies that

Let $A = \sum_{i = 1}^{d + 1} x_{k_i}$. Then we have

Since $A > x_k$ and $A \equiv x_1 \ (\mathrm{mod}\ {d})$, we see that $A = x_n$ for some $n > k$. But by (2.3), $A = x_n$ satisfies (2.1), contradicting the fact that $k$ is the largest integer such that $x_k$ satisfies (2.1).

Case 1.2 $\left\lfloor \alpha x_{k_{d+1}}\right\rfloor \equiv 0 \ (\mathrm{mod}\ {2})$. Let $M$ be the maximum value of $\left\{ \alpha x_{k_{i}} \right\}$ for $i = 1, 2, \ldots, d$. Since $d$ is even, we must have $d \geq 2$. Then

Therefore there are infinitely many $t \in \mathbb{N}$ such that

Then one of the two sets

is infinite, say $Y$. Then we can choose integers $t_d > t_{d - 1} > \cdots > t_1 > k$ in $Y$ so that

and

(If $X$ is infinite, then we can choose such $t_1, t_2, \ldots, t_d \in X$ too.) Let

Then

By (2.2) and (2.5), we obtain

which implies that

Similar to Case 1.1, we have

Therefore $B = x_n$ for some $n > k$ and $x_n$ satisfies (2.1), a contradiction.

Case 2. $d$ is odd. Let $k_{d+1}$ be an integer satisfying

This case is similar to Case 1. Let $D = \sum_{i = 1}^{d + 1} x_{k_i}$. Then $D > x_k$, $D \equiv x_1 \ (\mathrm{mod}\ {d})$, and

Since $k_{d+1} > k$ and $\{\alpha x_{k_{d+1}}\} < c$, we see that $\lfloor \alpha x_{k_{d+1}} \rfloor \equiv 1 \ (\mathrm{mod}\ {2})$. In addition, we have

From (2.6), (2.7), and (2.8), we obtain

Therefore $D = x_n$ for some $n > k$ and $x_n$ satisfies (2.1), a contradiction.

In any case, we have a contradiction. So the proof is complete.

Lemma 8. Suppose $a$ and $b$ are positive rational numbers and $a, b \neq 1$. Then $\log_{b} a$ is rational if and only if there exist integers $m$ and $n$ such that $a^m = b^n$.

Proof. This is well-known. For more details, see for example, pages 24–25, Chapter 2 in the book of Niven ^[27].

3.   Main results

We are now ready to prove our main theorems. We begin with maximal and minimal orders of $A_b (n)$.

Theorem 9. Let $b \geq 2$ be an integer. Then

In particular, a maximal order of $A_{b} (n)$ is $\left(\sqrt{b} + \frac{1}{\sqrt{b}} \right)\sqrt{n}$.

Proof. Let $\varepsilon > 0$. By Lemma 4, it remains to show that $A_b (n)/\sqrt{n} \geq \sqrt{b} + \frac{1}{\sqrt{b}} - \varepsilon$ for infinitely many $n \in \mathbb{N}$. To prove this, we construct a strictly increasing sequence $(n_k)_{k \geq 1}$ of positive integers such that

For each $k \in \mathbb{N}$, let $n_k = b^{2k+1}+1$. By Lemma 3, we obtain that $A_b (n_k) = b^{k+1}+b^k-1$. Therefore,

as desired.

Theorem 10. Let $b \geq 2$ be an integer. Then

In particular, a minimal order of $A_{b} (n)$ is $2 \sqrt{n}$.

Proof. Let $\varepsilon > 0$. We first show that $A_b (n)/\sqrt{n} \geq 2 - \varepsilon$ for all large $n$. Let $N$ be a large positive integer to be determined later and let $n \geq b^N$. Since $[b^N, \infty) = \bigcup_{k = N}^{\infty} [b^k, b^{k+1})$, we see that $b^k \leq n < b^{k+1}$ for some $k \geq N$. Then the number of digits of $n$ in its $b$-adic expansion is $k + 1$. Let

So $y = (a_k a_{k-1} \cdots a_{k - \left\lfloor \frac{k}{2} \right\rfloor} 00\cdots 0)_b$, $n \geq y$, and $A_{b} (n) \geq A_{b} (y)$. We divide the calculation into two cases according to the parity of $k$.

Case 1. $k$ is even. Then by Lemma 3,

Observe that

Then $\sqrt{n} \leq b^{k/2} \sqrt{z + \delta}$, where $\delta = b^{-k/2} - b^{-k} > 0$. Therefore

As $N \rightarrow \infty$, we see that $n \rightarrow \infty$, $k \rightarrow \infty$, and $\delta/\sqrt{z + \delta} \leq \sqrt{\delta} = \sqrt{b^{-\frac{k}{2}} - b^{-k}} \rightarrow 0$. Therefore we can choose $N$ large enough so that

Case 2. $k$ is odd. Some calculations in this part are similar to those in Case 1, so we skip some details. Let $\delta = b^{-(k-1)/2} - b^{-k} > 0$. By Lemma 3,

In addition,

In any case, we see that if $N$ is large and $n \geq b^N$, then $A_b (n)/\sqrt{n} \geq 2 - \varepsilon$. So it remains to show that $A_b (n)/\sqrt{n} \leq 2 + \varepsilon$ for infinitely many $n\in \mathbb{N}$. For each $k \in \mathbb{N}$, let $n = n_k = b^{2k} - 2$. Then $n = (a_{2k-1} a_{2k-2} \cdots a_1 a_0)_b$ where $a_0 = b-2$ and $a_i = b-1$ for all $i = 1, 2, \cdots, 2k-1$, and $n < b^{2k} - 1 = C_b (n)$. By Lemma 3, we have

This implies

Since $k$ is arbitrary, there are infinitely many $n \in \mathbb{N}$ such that $A_b (n)/\sqrt{n} \leq 2 + \varepsilon$. This completes the proof.

We used a computer to compare the values of $A_{b} (n)$ when $b = 2, 3, 5, 10$ and $n = 10^k$ for $k = 1, 2, \ldots, 20$. The data are shown in Table 1 at the end of this article. We see that for distinct $b, b_{1} \in \{2, 3, 5, 10\}$, there is an integer $n \geq 1$ such that $A_{b} (n) > A_{b_{1}} (n)$ and there is an integer $m \geq 1$ such that $A_{b} (m) < A_{b_{1}} (m)$. For example, $A_{2} (10^{20}) > A_{10} (10^{20})$ while $A_{2} (10^{19}) < A_{10} (10^{19})$. In general, we have the following theorem, which is the main result of this paper.

Theorem 11. Let $b > b_{1} \geq 2$ be integers. Then $A_{b} (n) - A_{b_{1}} (n)$ has infinitely many sign changes as $n \rightarrow \infty$. More precisely, the following statements hold.

${\rm(i)}$ There are infinitely many $n \in \mathbb{N}$ such that $A_{b_1} (n) > A_b (n)$.

${\rm(ii)}$ There are infinitely many $n \in \mathbb{N}$ such that $A_{b} (n) > A_{b_{1}} (n)$.

Proof. Throughout the proof, we apply Lemma 3 repeatedly without reference and separate the proof into two parts. In the first part, we show that (i) holds.

Case 1(i). $b$ is not a rational power of $b_{1}$. By Lemma 8, we see that $\log_{b} b_{1}$ is irrational. Applying Lemma 7 to the sequence of odd positive integers $(1, 3, 5, 7, \ldots)$ with $d = 2$, $\alpha = \log_{b} b_1$, and $c = \log_{b} \left(1 + \frac{1}{b^2} \right)$, we obtain that there are infinitely many integers $k$ such that

Let $k$ be one of those integers. Since $k \equiv 1 \ (\mathrm{mod}\ {2})$ and $b_{1}^k < b_{1}^k + 1 = C_{b_{1}} (b_{1}^k)$, we obtain

Next, we write $b_{1}^k = (a_r a_{r-1} \cdots a_1 a_0)_{b}$. Since $b^r \leq a_{r} b^r \leq b_{1}^k < b^{r + 1}$, we see that $r$ is the largest integer such that $b^r \leq b_{1}^k$. Therefore $r = \left\lfloor k \log_{b} b_{1} \right\rfloor \geq \left\lfloor 5\log_{b_{1}} b\cdot \log_{b} b_{1} \right\rfloor = 5$. In addition, $a_{r} b^r \leq b_{1}^k < (a_r + 1)b^r$, so $a_r$ is the largest integer such that $a_{r} b^r \leq b_{1}^k$. Therefore

Since $\left\{ k \log_{b} b_{1} \right\} < \log_{b} (1 + 1/b^2) < \log_{b} 2$, we see that $b^{\left\{ k \log_{b} b_{1} \right\}} < b^{\log_{b} 2} = 2$. Thus $\left\lfloor b^{\left\{ k \log_{b} b_{1} \right\}} \right\rfloor < 2$, which implies $a_r < 2$. So $a_r = 1$. Next, we calculate $a_{r-1}$. We see that

Since $\left\{ k \log_{b} b_{1} \right\} < \log_{b} \left(1 + 1/b^2 \right) \leq \log_{b} (1 + 1/b)$, we have

We obtain from (3.3) that $a_{r - 1} < b+ 1 - b = 1$, which implies $a_{r-1} = 0$. Similarly, we have

This implies $a_{r-2} = 0$. So we have $a_r = 1$ and $a_{r-1} = a_{r - 2} = 0$, and thus $b_{1}^k \leq b^r + b^{r-2}$. Recall that $r = \left\lfloor k \log_{b} b_{1} \right\rfloor \equiv 0 \ (\mathrm{mod}\ {2})$, $r \geq 5$, and $b^r \leq b_{1}^k$. Since $b^{r} + b^{r-2} < b^{r} + b^{r-2} + b^2 + 1 = C_{b} (b^{r} + b^{r-2})$, we obtain

From this and (3.2), we obtain

Since $b > b_{1} \geq 2$ and the function $x \mapsto \sqrt{x} + \frac{1}{\sqrt{x}}$ is increasing on $[1, \infty)$,

Therefore $A_{b_{1}} (b_{1}^k) - A_{b} (b_{1}^k) > 0$. Since $A_{b_{1}} (b_{1}^k) - A_{b} (b_{1}^k) > 0$ holds for any $k$ satisfying (3.1), we can choose $n = b_{1}^k$ and obtain that $A_{b_{1}} (n) - A_{b} (n) > 0$ for infinitely many $n$, as required.

Case 2(i). $b$ is a rational power of $b_1$. Let $b^{s} = b_{1}^t$ for some $s, t \in \mathbb{N}$ with $\gcd(s, t) = 1$. Let $m \in \mathbb{N}$ and $k = 2mt + 1$. Then $k$ is odd. Since $b_{1}^k + 1 = C_{b_{1}} (b_{1}^k + 1)$, we obtain

Since $b^{s} = b_{1}^t$ and $k = 2mt + 1$, we obtain $b_{1}^k = b_{1}^{2mt + 1} = b_{1}\cdot b^{2ms}$. Therefore $b_{1}^k + 1 = (a_r a_{r-1} \cdots a_0)_b$ where $r = 2ms$, $a_r = b_1$, $a_0 = 1$, and $a_i = 0$ for $i = 1, 2, \ldots, r-1$. So

From this and (3.5), we obtain $A_{b_{1}} (b_{1}^k + 1) - A_{b} (b_{1}^k + 1) = 1$. Since $m$ is arbitrary, we can choose $k = 2mt + 1$ and $n = b_{1}^k + 1$ so that $A_{b_{1}} (n) - A_{b} (n) > 0$ for infinitely many $n$.

Case 1(i) and Case 2(i) give a proof of (i). The proof of (ii) is quite similar to that of (i). So we omit some details. We divide the consideration into two cases.

Case 1(ii). $b$ is not a rational power of $b_{1}$. Then $\log_{b_{1}} b$ is irrational. Similar to Case 1(i), we apply Lemma 7 and let $k$ be an integer such that

Then

We write $b^k = \left(a_r a_{r-1} \cdots a_1 a_0 \right)_{b_{1}}$. Then $r = \left\lfloor k \log_{b_{1}} b\right\rfloor \geq k \geq 5$ and

which implies $a_r = 1$. Similarly,

which implies $a_{r-1} = 0$. Then

which implies $a_{r-2} = 0$. So $b^k \leq b_{1}^r + b_{1}^{r-2} < C_{b_{1}} \left(b_{1}^{r} + b_{1}^{r-2} \right)$. Recall that $r = \left\lfloor k\log_{b_{1}} b\right\rfloor \equiv 0 \ (\mathrm{mod}\ {2})$ and $r \geq 5$. Then

From this and (3.7), we obtain

Since $b > b_{1} \geq 2$ and the function $x \mapsto \sqrt{x} + \frac{1}{\sqrt{x}}$ is increasing on $[1, \infty)$, we have

Therefore $A_{b} (b^k) - A_{b_{1}} (b^k) > 0$. By Lemma 7, there are infinitely many integers $k$ satisfying (3.6). So we can choose $n = b^k$ so that $A_{b} (n) - A_{b_{1}} (n) > 0$ for infinitely many $n$.

Case 2(ii). $b^s = b_{1}^t$ for some $s, t \in \mathbb{N}$ with $\gcd(s, t) = 1$. Let $m \in \mathbb{N}$ and $k = 2ms + 1$. Then $k$ is odd and

Since $b^s = b_{1}^t$, we obtain $b^k = b^{2ms + 1} = b_{1}^{2mt} b_{1}^{\frac{t}{s}} = b_{1}^{\left\{\frac{t}{s}\right\}} \cdot b_{1}^{2mt + \left\lfloor \frac{t}{s} \right\rfloor}$. Since $\left\{ \frac{t}{s} \right\} = \frac{j}{s}$ for some $j = 0, 1, \ldots, s-1$, we obtain $b_{1}^{\left\{ \frac{t}{s} \right\}} = b_{1}^{\frac{j}{s}}$. Recall that for any positive integers $x$ and $y$, $x^{1/y}$ is either an irrational number or an integer. Then $b_{1}^{\left\{\frac{t}{s}\right\}} = \left(b_{1}^j \right)^{\frac{1}{s}}$ is either an irrational number or an integer. If $b_{1}^{\left\{\frac{t}{s}\right\}}$ is irrational, then $b = b_{1}^{\frac{t}{s}} = b_{1}^{\left\{\frac{t}{s}\right\}} \cdot b_{1}^{\left\lfloor \frac{t}{s} \right\rfloor}$ is irrational, a contradiction. So $b_{1}^{\left\{\frac{t}{s}\right\}} \in \mathbb{N}$ and $b^k = (a_r a_{r-1} \cdots a_0)_{b_{1}}$ where $r = 2mt + \left\lfloor \frac{t}{s} \right\rfloor$, $a_r = b_{1}^{\left\{ \frac{t}{s} \right\}} = b_{1}^{\frac{j}{s}}$, and $a_{i} = 0$ for all $i = 0, 1, \ldots, r-1$. Therefore

In addition, $b^{\frac{k}{2}} = b^{ms + \frac{1}{2}} = b_{1}^{mt + \frac{t}{2s}}$. Suppose first that $\left\lfloor \frac{t}{s} \right\rfloor$ is even. Then

Since $b > b_{1}^{\frac{j}{s}} \geq 1$ and the function $x \mapsto \sqrt{x} + \frac{1}{\sqrt{x}}$ is strictly increasing on $[1, \infty)$, we obtain from (3.9) and (3.10) that

Suppose $\left\lfloor \frac{t}{s} \right\rfloor$ is odd. Then similar to (3.10), we obtain

where $\ell = 1 - \left\{ \frac{t}{s} \right\}$. From this and (3.9), we obtain

Since $m$ is arbitrary, we can choose $k = 2ms + 1$ and $n = b^k$ so that $A_{b} (n) - A_{b_{1}} (n) > 0$ for infinitely many $n$.

Case 1(ii) and Case 2(ii) give a proof of (ii). Therefore the proof of this theorem is complete.

Observing the proof of Theorem 11 carefully, we can state some parts of Theorem 11 in a stronger form as follows.

Theorem 12. Let $b > b_{1} \geq 2$ be integers. Then the following statements hold.

${\rm(i)}$ There are infinitely many $k \in \mathbb{N}$ and a constant $c > 0$ depending at most on $b$ and $b_{1}$ and not on $k$ such that

Consequently, $\limsup_{n \rightarrow \infty} \left(A_{b} (n) - A_{b_{1}} (n) \right) = + \infty$.

${\rm(ii)}$ Suppose $b$ is not a rational power of $b_1$. Then there are infinitely many $k \in \mathbb{N}$ and a constant $d > 0$ which depends at most on $b$ and $b_{1}$ and not on $k$ such that

Consequently, $\liminf_{n \rightarrow \infty} \left(A_{b} (n) - A_{b_{1}} (n) \right) = - \infty$

Proof. For (i), we consider Case 1(ii) and Case 2(ii) in the proof of Theorem 11. In Case 1(ii), we see from (3.8) that we can take $c = \sqrt{b} + \frac{1}{\sqrt{b}} - 2 - \frac{1}{b_{1}^2}$ so that $A_{b} (b^k) - A_{b_{1}} (b^k) \geq c b^{\frac{k}{2}}$. Next, we consider (3.11) and (3.12) in Case 2(ii). Let $0 < \alpha < 1$. Since $b_{1} > b_{1}^{\alpha} \geq 1$ and the function $x \mapsto \sqrt{x} + \frac{1}{\sqrt{x}}$ is increasing on $[1, \infty)$, we obtain

Setting $\alpha = \frac{j}{s}$ in (3.11) and let $\alpha = \ell$ in (3.12), we see that we can take

so that

If we would like to obtain $c$ that works in (3.8), (3.11), and (3.12), then we can choose

This proves (i). For (ii), we consider (3.4) in Case 1(i), take $d = \sqrt{b_{1}} + \frac{1}{\sqrt{b_{1}}} - 2 - \frac{1}{b^{2}}$, and obtain that

This proves (ii). So the proof is complete.

We are now ready to give a complete answer to Vepir's question ^[32] posted on Mathematics Stack Exchange. The title of Vepir's post is as follows:

In the comment, Vepir also says that he is only interested in the palindromes having more than one digit. Therefore for each integers $b \geq 2$ and $n \geq 1$, we let

So $f_{b} (n)$ is the number of $b$-adic palindromes which have more than one digit and are less than or equal to $n$. We have the following corollary.

Corollary 13. Let $b > b_{1} \geq 2$ be integers. Then $f_{b} (n) - f_{b_{1}} (n)$ changes sign infinitely often as $n \rightarrow \infty$. In other words, if we use counting measure, then the races between palindromes in any two different bases have infinitely many wins and infinitely many losses.

Proof. By Theorem 11, there are infinitely many $n \in \mathbb{N}$ such that $A_{b_{1}} (n) > A_{b} (n)$. So if $n$ is such an integer, then

By Theorem 12, there are infinitely many $m \in \mathbb{N}$ such that $A_{b} (m) - A_{b_{1}} (m) \geq b$. So if $m$ is such an integer, then

This completes the proof.

Corollary 14. Let $b > b_{1} \geq 2$ be integers. Then $A_{b} (n) - A_{b_{1}} (n) = 0$ for infinitely many $n \in \mathbb{N}$.

Proof. For each $n \in \mathbb{N}$, let $g(n) = A_{b} (n) - A_{b_{1}} (n)$. We know that, for any $n \in \mathbb{N}$, both $A_{b} (n+1) - A_{b} (n)$ and $A_{b_{1}} (n+1) - A_{b_{1}} (n)$ are either 0 or 1. So $g(n + 1) - g(n)$ is $-1, 0$, or $1$, that is, the difference of any two consecutive terms of the sequence $(A_{b} (n) - A_{b_{1}} (n))_{n \geq 1}$ is one of $-1$, $0$, or $1$. Therefore if $A_{b} (r) - A_{b_{1}} (r) < 0$ and $A_{b} (m) - A_{b_{1}} (m) > 0$, then there exists an integer $n$ lying between $r$ and $m$ such that $A_{b} (n) - A_{b_{1}} (n) = 0$. By Theorem 11, there are infinitely many $n \in \mathbb{N}$ such that $A_{b} (n) - A_{b_{1}} (n) = 0$, as required.

4.   Conclusion and some future projects

We obtain extremal orders of the palindromes counting function $A_b(n)$ and show that if $b > b_1\geq 2$, then $A_b(n)-A_{b_1}(n)$ has infinitely many sign changes as $n\to \infty$. Moreover, we obtain that

and if $b$ is not a rational power of $b_1$, then

Problem 1. Suppose $b > b_1$ and $b$ is a rational power of $b_1$. Then, perhaps, $\liminf_{n\to\infty} \left(A_b(n)-A_{b_1}(n)\right)$ is either $-\infty$ or $-1$. More precisely, it is $-1$ if and only if $b$ is an integral power of $b_1$, and it is $-\infty$ if and only if $b\neq b_1^m$ for any $m\in \mathbb N$. We do not have a proof of this yet but we plan to do it in the future.

Problem 2. Suppose $b_1, b_2, \ldots, b_k$ are distinct integers larger than $1$. We believe that our results can be extended to the string of inequalities

for infinitely many $n\in \mathbb N$. Maybe, if $\delta_i\in \{0, 1, -1\}$ for every $i$, $\delta_1+\delta_2+\cdots+\delta_k = 0$, and $b_1, b_2, \ldots, b_k$ satisfy some natural conditions such as $\log b_i/\log b_j$ is not rational for any $i\neq j$, then

Problem 3. For positive integers $b\geq 2$, $n\geq 1$, $q\geq 2$, and $1\leq a \leq q$, let $A_b(n, q, a)$ be the number of $b$-adic palindromes which are less than or equal to $n$ and are congruent to $a$ modulo $q$. Perhaps, we can find an asymptotic formula for $A_b(n, q, a)$. Then the study of the race between palindromes in different congruence classes (in the same or different bases) may be interesting. For example, under some natural conditions on $b$ and $q$, are there infinitely many sign changes in $A_b(n, q, a_1)-A_b(n, q, a_2)$ for distinct $a_1$, $a_2$? If $k\in \mathbb N$ is fixed, are there $b$, $q$, $a_1$, $a_2$ such that the number of sign changes in $A_b(n, q, a_1)-A_b(n, q, a_2)$ is exactly $k$?

Problem 4. Can Lemma 7 be extended to any congruence classes? For example, suppose $(x_n)$ is an arithmetic progression, $x_n\in \mathbb Z$ for all $n\in \mathbb N$, $d = x_2-x_1\geq 1$, $\alpha$ is an irrational number, and $0\leq c_1 < c_2\leq 1$. Then for any $q\geq 2$ and $0\leq a < q$, we may be able to prove that there are infinitely many $k\in \mathbb N$ such that $c_1 < \{\alpha x_k\} < c_2$ and $\left\lfloor \alpha x_k\right\rfloor\equiv a\pmod q$. Furthermore, we may be able to replace the assumption that $x_n\in \mathbb Z$ for all $n\in \mathbb N$ by a weaker condition.

Problem 5. Considering Remark 3.19 in the article by Kawsumarng et al. ^[22], we see that there exists a palindromic pattern in the sumset $B(\alpha^2)+B(\alpha^2)$ with respect to the Fibonacci numbers, where $B(\alpha^2)$ is the upper Wythoff sequence. It may be interesting to see whether or not these kinds of palindromic patterns occur in the $h$-fold sumset $hB(x)$ with respect to the members of linear recurrence sequence $(a_n)$, where $x$ is a particular root of the characteristic polynomial of the sequence $(a_n)$ and $h+1$ is the smallest positive integer such that $(h+1)B(x)$ is cofinite.

We plan to solve some of these problems in the future but we do not mind if the readers solve them before us.

Acknowledgments

We are grateful to the editor and reviewers for their comments and suggestions which improve the quality of this article. 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.

Conflict of interest

The authors declare that there is no conflict of interests regarding the publication of this article.

Appendix