A complete comparison for the number of 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$. Throughout this article, we let $A_b (n)$ be the number of $b$-adic palindromes not exceeding $n$.

Previously, we ^[1] obtained an extremal order of $A_{b} (n)$ and proved that if $b > b_{1} \geq 2$ are integers, then

In addition, if $\frac{\log b}{\log b_{1}}$ is irrational, then

Therefore, it is interesting to determine the value of the left-hand side of (1.1) when $b$ is a rational power of $b_{1}$. In this article, we show in Theorem 3.1 that if $\log b / \log b_{1}$ is an integer, then the left-hand side of (1.1) is $-1$, and we obtain in Theorem 3.2 that if $\log b / \log b_{1}$ is rational but not integral, then the left-hand side of (1.1) is $- \infty$. We also propose some possible research problems at the end of this article. We remark that the study on the ratio $A_b (n)/ A_{b_1} (n)$ may be interesting too, but we were previously interested in the sign changes of $A_b (n) - A_{b_1} (n)$, and so we focus only on the difference not the ratio. Nevertheless, since $A_b (n) - A_{b_1} (n)$ has an infinite number of sign changes, if the limit of $A_b (n)/ A_{b_1} (n)$ as $n \rightarrow \infty$ exists, then it must be one.

Perhaps, one of the popular problems in palindromes is to determine whether or not there are infinitely many palindromic primes. Although this problem is still open, Banks, Hart and Sakata ^[2] showed that almost all palindromes in any fixed base $b \geq 2$ are composite. Banks and Shparlinski ^[3] also obtained results on prime divisors of palindromes, and there are many other interesting articles on palindromes too. We refer the reader to Banks ^[4], Cilleruelo, Luca and Baxter ^[5], and Rajasekaran, Shallit and Smith ^[6] for additive properties of palindromes, Bašić ^[7,8], Di Scala and Sombra ^[9], Goins ^[10], Luca and Togbé ^[11] for the study of palindromes in different bases, Cilleruelo, Luca and Tesoro ^[12] for palindromes in linear recurrence sequences, Harminc and Soták ^[13] for $b$-adic palindromes in arithmetic progressions, and Pongsriiam ^[14] for the longest arithmetic progressions of palindromes.

2.   Preliminaries and lemmas

In this section, we provide some results 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$. It is also convenient to define $C_b (n)$ as follows.

Definition 2.1. Let $b \geq 2$ and $n = (a_k a_{k - 1} \cdots a_{1} a_0)_b$ be positive integers. We 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 - \left\lfloor k/2 \right\rfloor \leq i \leq k$. In other words, $C_b (n)$ is the $b$-adic palindrome having $k+1$ digits whose first half digits 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$.

In the following lemma, if $P$ is a mathematical statement, then the Iverson notation $[P]$ is defined by $[P] = 1$ if $P$ holds, and $[P] = 0$ otherwise. Then the formula for $A_b (n)$ is as follows.

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

Lemma 2.2. Let $a, r, s \geq 2$ be integers and $(r, s) = 1$. If $a^{\frac{r}{s}}$ is an integer, then there exists an integer $c \geq 2$ such that $a = c^s$.

Proof. Suppose $a^{\frac{r}{s}} = m$ is an integer. Then $a^r = m^s$, and so $a$ and $m$ have the same set of prime divisors. Let $a = \prod_{i = 1}^{k} p_{i}^{a_{i}}$ and $m = \prod_{i = 1}^{k} p_{i}^{m_{i}}$. Then $a_{i} r = m_{i} s$ for all $i$. Since $s \mid a_{i} r$ and $(s, r) = 1$, $s \mid a_{i}$ for all $i$. Let $c = \prod_{i = 1}^{k} p_{i}^{a_i/s}$. Then $c$ is an integer, $c \geq 2$, and $a = c^s$. So the proof is complete.

3.   Main results

Theorem 3.1. Let $b > b_1 \geq 2$ and $\ell \geq 2$ be integers. Suppose that $b = b_{1}^{\ell}$. Then, the following statements hold.

$\textrm{(i)}$ $A_{b} (n) - A_{b_1} (n) \geq -1$ for all $n \in \mathbb{N}$.

$\textrm{(ii)}$ $A_{b} (n) - A_{b_1} (n) = -1$ for infinitely many $n \in \mathbb{N}$.

$\textrm{(iii)}$ $\liminf\limits_{n \rightarrow \infty} \left(A_{b} (n) - A_{b_{1}} (n)\right) = -1$.

Proof. We first prove (i). Let $n \geq 1$ and write

Since $b^{r} \leq c_{r} b^{r} \leq n < b^{r + 1}$, we see that $r = \left\lfloor \frac{\log n}{\log b} \right\rfloor$. Similarly, we have $k = \left\lfloor \frac{\log n}{\log b_{1}} \right\rfloor$, and so $r = \left\lfloor k/\ell \right\rfloor$. By the uniqueness of the $b$-adic and $b_1$-adic representations, we can write $c_0$, $c_1$, $c_2, \ldots,$ $c_r$ in terms of $b_1$ and the $a_j$ as follows:

Considering $n$ modulo $b$, we obtain

and both sides of the congruence are nonnegative integers less than $b$, and so they are equal. Similarly, after reducing $n$ modulo $b^2, b^3, \ldots, b^{r + 1}$, respectively, we obtain $c_1, c_2, \ldots c_{r}$. Thus

where $a_{m} = 0$ if $m > k$. By Lemma 2.1, we have

It is useful to recall that if $k\in\mathbb{Z}$ and $x\in\mathbb{R}$, then $\lfloor k+x\rfloor = k + \lfloor x\rfloor$, and if $k\in\mathbb{N}$ and $x\in\mathbb{R}$, then $\left\lfloor\frac{\lfloor x\rfloor}{k}\right\rfloor = \left\lfloor\frac{x}{k}\right\rfloor$. We also let $s = k \bmod{\ell}$ be the least nonnegative residue of $k$ modulo $\ell$, that is, $k \equiv s \pmod{\ell}$ and $0 \leq s < \ell$. Then, from (3.1) and (3.2), we obtain

Next, we will reduce the double sum in (3.4) into a sum. We see that if $\left\lfloor \frac{k}{\ell} \right\rfloor$ is even, then $- \ell j + i$ runs through the integers from $- \frac{k - s}{2}$ to $\ell - 1$ exactly once as $j$ runs through $0, 1, 2, \ldots, \frac{k - s}{2\ell}$ and $i$ runs through $0$ to $\ell - 1$. Similarly, if $\left\lfloor \frac{k}{\ell} \right\rfloor$ is odd, then $- \ell j + i$ ranges over the integers from $- \frac{k - s - \ell}{2}$ to $\ell - 1$ exactly once as $j$ ranges over $0, 1, 2, \ldots, \frac{k - s - \ell}{2\ell}$ and $i$ ranges over $0$ to $\ell - 1$. So if $\left\lfloor \frac{k}{\ell} \right\rfloor$ is even, the first double sum in (3.4) reduces to

We replace the index $i$ by $i - \frac{k - s}{2}$ and recall that $s \leq \ell - 1$, $a_{\frac{k - s}{2} + i} = 0$ if $i > \frac{k + s}{2}$, and $\ell - 1 + \frac{k - s}{2} \geq \frac{k + s}{2}$. So the first double sum in (3.4) further reduces to

Similarly, if $\left\lfloor \frac{k}{\ell} \right\rfloor$ is odd, then the second double sum in (3.4) reduces to

From (3.4) and the above calculation, we obtain

Next, we divide the proof into four cases according to the parity of $k$ and $\left\lfloor \frac{k}{\ell} \right\rfloor$.

Case 1. Assume that $k$ and $\left \lfloor \frac{k}{\ell} \right\rfloor$ are even. Then, $s$ is even and

By (3.3), (3.5) and the above inequality, we obtain that $A_b (n) - A_{b_1} (n)$ is at least

Since the function $x \mapsto a_{k} x + x^{-1}$ is increasing on $[1, \infty)$, the number in the above parenthesis is nonnegative, and so $A_b (n) - A_{b_1} (n) \geq -1$.

Case 2. Assume that $k$ is odd and $\left\lfloor \frac{k}{\ell} \right\rfloor$ is even. Then $s$ is odd. Similar to Case 1, we obtain

By (3.3), (3.5) and the above inequality, we see that $A_{b} (n) - A_{b_1} (n)$ is at least

Since $x \mapsto a_{k} x + x^{-1}$ is increasing on $[1, \infty)$ and $b_{1}^{\frac{s}{2}} \geq b_{1}^{\frac{1}{2}} \geq 1$, we have $a_{k} b_{1}^{\frac{s}{2}} + b_{1}^{- \frac{s}{2}} \geq a_{k} b_{1}^{\frac{1}{2}} + b_{1}^{-\frac{1}{2}}$, and

Case 3. Assume that $k$ is even and $\left\lfloor \frac{k}{\ell} \right\rfloor$ is odd. Then $\ell \equiv k - s \equiv s \pmod{2}$. So $\frac{\ell - s}{2}$ is an integer and $\frac{\ell - s}{2} > 0$. So $\frac{\ell - s}{2} \geq 1$. Considering the first sum in (3.3) and changing the index from $i$ to $\frac{k + s - \ell}{2} - i$, we see that

By (3.3), (3.5) and the above inequality, we obtain

The sum on the right-hand side of (3.6) is less than or equal to $b_{1}^{\frac{k + s -\ell}{2} + 1} - 1$ and $1 - b_{1}^{\frac{\ell - s}{2}}$ is negative. Therefore, $A_{b} (n) - A_{b_1} (n)$ is at least

Since the function $x \mapsto b_{1}^{x} + b_{1}^{1 - x}$ is increasing on $[1, \infty)$ and $\frac{\ell - s}{2} \geq 1$, the number in the above parenthesis is nonnegative, and so $A_{b} (n) - A_{b_1} (n) \geq - 1$.

Case 4. Assume that $k$ and $\left \lfloor \frac{k}{\ell} \right\rfloor$ are odd. Changing the index from $i$ to $\frac{k - 1}{2} - \frac{\ell - s - 1}{2} - i$, the second sum in (3.3) is

By (3.3), (3.5) and the above inequality, we obtain that $A_{b} (n) - A_{b_{1}} (n)$ is at least

Since $x + x^{-1} \geq 2$ for all $x > 0$, we see that $A_{b} (n) - A_{b_{1}} (n) \geq -1$.

In any case, we obtain $A_{b} (n) - A_{b_1} (n) \geq -1$, as desired. This proves (i).

Next, we prove (ii). For each $k \in \mathbb{N}$, let $n = n_{k} = b_{1}^{2\ell k - 1} + 1$. Then $n = b_{1}^{\ell - 1} b^{2k - 1} + 1$. By Lemma 2.1, we obtain

Therefore $A_{b} (n) - A_{b_1} (n) = -1$. Since $n = n_k$ and $k$ is arbitrary, this shows that there are infinitely many $n \in \mathbb{N}$ such that $A_{b} (n) - A_{b_1} (n) = -1$. This proves (ii). Then (iii) follows immediately from (i) and (ii). So the proof is complete.

Since we have already got the answers to the cases when $\log b/ \log b_{1}$ is irrational and when it is integral, it remains to consider the case when $\log b / \log b_{1}$ is a rational number and is not an integer.

Theorem 3.2. Let $b > b_1 \geq 2$ be integers and $b = b_{1}^{\frac{r}{s}}$ where $r, s \in \mathbb{N}$, $r > s > 1$, and $(r, s) = 1$. Then

Proof. To prove this theorem, it is enough to find a sequence $(n_k)_{k \geq 1}$ of positive integers such that $n_k \rightarrow + \infty$ and $A_{b_{1}} (n_k) - A_{b} (n_k) \rightarrow + \infty$ as $k \rightarrow + \infty$. We divide the calculation into three cases according to parity of $r$ and $s$, and adjust the exponents so that $A_{b_1} (n)$ is large and $A_{b} (n)$ is small.

Case 1. Assume that $s$ is even. Let $k$ be a positive integer and $n = n_{k} = b^{s (2k + 1)} + 1$. Since $(r, s) = 1$, $s$ is even, and $b_{1}^{r} = b^{s}$, we see that $r$ is odd and $n = b_{1}^{r (2k + 1)} + 1$. By Lemma 2.1, we obtain $A_{b} (n) = 2b^{sk + \frac{s}{2}} - 1$ and

Since $x + x^{-1} > 2$ for all $x > 1$, we see that $b_{1}^{\frac{1}{2}} + b_{1}^{- \frac{1}{2}} - 2$ is a positive constant. Therefore,

Case 2. Assume that $s$ and $r$ are odd. Since $b_{1}^{\frac{r}{s}} = b$ is an integer, we obtain by Lemma 2.2 an integer $b_{2} \geq 2$ such that $b_{1} = b_{2}^{s}$, and so $b = b_{2}^{r}$. Since $(2s, r) = 1$, there exists a negative integer $x$ such that $2sx \equiv 1 \pmod{r}$. Since the proof of Case 1 is finished, we will define a new sequence $(n_{k})_{k \geq 1}$ using the same notation. Let $k$ be a positive integer and let $n = n_{k} = b_{1}^{2x (1 - s) + 2rk + 1} + 1$. For convenience, let $\ell = x(1 - s) + rk$. So $\ell \in \mathbb{N}$, $\ell \geq 5$, and $n = b_{1}^{2\ell + 1} + 1$. By Lemma 2.1 and the fact that $b_{1} = b_{2}^{s}$, we obtain

Next, let $y = \frac{s (2 \ell + 1) - 1}{r}$. By the definition of $\ell$ and $x$, we have

Therefore $y$ is a positive integer. Since $s(2 \ell + 1) - 1$ is even and $r$ is odd, we see that $y$ is even. To calculate $A_{b} (n)$, we write

So $b_{2}$ is the leading digit in the $b$-adic representation of $n$. Since $y$ is even and $b = b_{2}^{r}$, we obtain by Lemma 2.1 that

From (3.7) and (3.8), we obtain

Since the function $x \mapsto x + x^{-1}$ is strictly increasing on $(1, \infty)$ and $b_{2}^{\frac{s}{2}} > b_{2}^{\frac{1}{2}} > 1$, we see that $B$ is a positive constant. Therefore, $A_{b_{1}} (n) - A_{b} (n) = b_{2}^{s\ell + \frac{s}{2}}B + 1 \rightarrow + \infty$ as $\ell \rightarrow + \infty$. Since $\ell = x(1 - s) + rk \geq k$, we see that $A_{b_1} (n) - A_{b} (n) \rightarrow + \infty$ as $k \rightarrow + \infty$. So the proof of Case 2 is complete.

Case 3. Assume that $s$ is odd and $r$ is even. This case is similar to Case 2 and we only need to modify some calculations. Again, we have $b_{1} = b_{2}^s$ and $b = b_{2}^{r}$ for some integer $b_{2} \geq 2$. Since $(2r, 2s) = 2$ and $2 \mid 1 - s$, there exists a positive integer $k$ such that

In fact, there are infinitely many positive integers $k$ satisfying (3.9), so we can choose $k$ to be arbitrarily large. Let $n = n_{k} = b_{1}^{2k + 1} + 1$. By Lemma 2.1 and the fact that $b_{1} = b_{2}^{s}$, we obtain

Next, let $y = \frac{s(2k + 1) - 1}{r}$. By (3.9), we have $s(2k + 1) = 2sk + s \equiv 1 \pmod{2r}$. Therefore $2r$ divides $s(2k + 1) - 1$, and thus $y = 2 \left(\frac{s(2k + 1) - 1}{2r} \right)$ is an even positive integer. To calculate $A_{b} (n)$, we write

By Lemma 2.1, we obtain

From (3.10), (3.11) and a similar reason as in Case 2, we obtain

This completes the proof.

4.   Conclusions

Let us record all related results that we obtained as follows.

Summary of the results:

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

(i) If $\frac{\log b}{\log b_{1}}$ is not an integer, then,

(ii) If $\frac{\log b}{\log b_{1}}$ is an integer, then,

(iii) $A_{b} (n) - A_{b_{1}} (n)$ has an infinite number of sign changes as $n \rightarrow \infty$.

(iv) If $s_{b}$ and $s_{b_{1}}$ are the sums of the reciprocal of palindromes in bases $b$ and $b_{1}$, respectively, then $s_b$ and $s_{b_1}$ are finite and $s_{b} > s_{b_{1}}$.

The statements (i)–(iii) come directly from [1, Theorems 11 and 12], and Theorems 3.1 and 3.2 of this article. The finiteness of $s_b$ and $s_{b_1}$ in (iv) is given by Shallit and Klauser ^[16] and the inequality $s_b > s_{b_1}$ is obtained from [17, Theorem 3].

Now that for all cases we have obtained results for the comparison between the number of palindromes in two bases, it is natural to extend this to more than two bases. So let $k \geq 2$ and $b_{1} > b_{2} > \cdots > b_{k} \geq 2$ be integers. Let $c_1, c_2, \ldots, c_k$ be any permutation of $b_{1}, b_2, \ldots, b_{k}$.

Question 4.1. Does the inequality $A_{c_1}(n) < A_{c_2}(n) < \cdots < A_{c_k}(n)$ hold for infinitely many $n \in \mathbb{N}$? We conjecture that if $\log b_{i}/ \log b_{j}$ is irrational for every distinct $i, j = 1, 2, \ldots, k$, then the inequality holds for infinitely many $n \in \mathbb{N}$. What are the answers when one of the following situations occur?

(i) $\frac{\log b_i}{\log b_{i + 1}}$ is integral for every $i = 1, 2, \ldots, k-1$;

(ii) $\frac{\log b_i}{\log b_{j}}$ is rational but not integral for each distinct $i$, $j$;

(iii) The set $\left\{ \left. \frac{\log b_i}{\log b_j} \ \right|\ 1\leq i < j \leq k \right\}$ contains both an irrational number and a rational number.

Acknowledgments

Prapanpong Pongsriiam's research project is funded jointly by the Faculty of Science Silpakorn University and the National Research Council of Thailand (NRCT), grant number NRCT5-RSA63021-02. He is 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.

Conflict of interest

The authors declare no conflicts of interest regarding the publication of this article.\newpage