Palindromes and Antipalindromes in Short Intervals

Prapanpong Pongsriiam^{1} Department of Mathematics Faculty of Science Silpakorn University Nakhon Pathom 73000 Thailand

                 prapanpong@gmail.com
               pongsriiam p@silpakorn.edu

Kota Saito Faculty of Pure and Applied Sciences University of Tsukuba 1-1-1 Tennodai, Tsukuba Ibaraki, 305-8577 Japan

             saito.kota.gn@u.tsukuba.ac.jp

Abstract

For each positive integer b larger than 1, we obtain the shortest intervals that always contain a b-adic palindrome and a b-adic antipalindrome. We also give some results on the classification of b-adic twin palindromes, gaps that occur infinitely often between b-adic palindromes, and the irrationality of the sum of reciprocals of a particular type of b-adic palindrome.

1Prapanpong Pongsriiam is the corresponding author.

1 Introduction

Let b and n be integers, b ≥ 2, and n ≥ 1, and let n = (n_{k}n_{k−1} ⋯ n_{0})_{b} be the b-adic expansion of n with n_{k} ≠ 0. We call n a palindrome in base b (or b-adic palindrome) if n_{k−i} = n_{i} for 0 ≤ i ≤ ⌊k/2⌋. As usual, if we write a number without specifying the base, then it is always in base 10, and if we write n = (n_{k}n_{k−1} ⋯ n_{0})_{b}, then it means that n = ∑_{i=0}^{k} n_{i}b^{i}, n_{k} ≠ 0, and 0 ≤ n_{i} < b for all i = 0, 1, …, k. The sequence of 10-adic palindromes and the sequence of palindromic primes in base 10 are given, respectively, as \underline{A002113} and \underline{A002385} in the On-Line Encyclopedia of Integer Sequences (OEIS) [13]. In addition, we write ⌊x⌋ for the greatest integer less than or equal to x and ⌈x⌉ for the least integer larger than or equal to x. It seems that there is more than one intuitive definition for antipalindromic structure, so we will try to cover more than one, too. Suppose that n is a b-adic antipalindrome of a particular type, to be defined below. We say that

n is of type 0 (or no middle type) if k is odd and n_{k−i} + n_{i} = b − 1 for 0 ≤ i ≤ ⌊k/2⌋; n is of type 1 (or one middle type) if n_{k−i} + n_{i} = b − 1 for 0 ≤ i ≤ ⌊k/2⌋; n is of type 2 (or free middle type) if n_{k−i} + n_{i} = b − 1 for 0 ≤ i ≤ ⌊(k − 1)/2⌋; n is of type 3 (or asymmetric type) if n_{k−i} ≠ n_{i} for 0 ≤ i ≤ ⌊(k − 1)/2⌋.

If 1 ≤ n < b, then k = 0 and n is defined to be a b-adic antipalindrome of types 2 and 3. When k is odd, types 0, 1, and 2 are the same; when k is even, they are different, as it is necessary that b is odd and 2n_{\frac{k}{2}} = b − 1 for type 1 (one middle type), but there is no restriction on b and n_{\frac{k}{2}} for type 2 (free middle type). We remark that types 0 and 1 appear in the work of Bai, Meleshko, Riasat, and Shallit [2] and Dvořáková, Kruml, and Ryzak [6]. Type 3 (asymmetric type) is modified from the notion of antipalindromic composition in the article by Andrews, Just, and Simay [1], and a generalization by Huang [7]. Type 2 uses the equality n_{k−i} + n_{i} = b − 1 as in types 0 and 1, and the index condition i ≤ ⌊(k − 1)/2⌋ as in type 3. The sequence of binary antipalindromes of type 0 is given as \underline{A035928} in OEIS [13].

The interval (n^{2}, (n + 1)^{2}] obviously contains a square, and Legendre conjectured that it also contains a prime for all large n ∈ ℕ, but this is still open. Replacing the existence or nonexistence of primes and squares in the interval such as (n^{2}, (n + 1)^{2}] by that of b-adic palindromes and b-adic antipalindromes leads to an easier problem than that of the primes, but less obvious and more interesting than that of squares. We should remark here that the analogy between primes and palindromes is artificial; we mention it merely for the form of questions being asked. Nevertheless, by Phunphayap and Pongsriiam’s results [9, Theorems 9–10], we see that if A_{b}(x) and s(x) are, respectively, the number of b-adic palindromes and squares less than or equal to x, then A_{b}(x) ≍ s(x). Here, if f(x) and g(x) are positive for all large x, then we write f(x) ≍ g(x) to mean that there are constants c_{1}, c_{2} > 0 such that c_{2}g(x) ≤ f(x) ≤ c_{1}g(x) for all large x. This motivates us to compare or find a connection between squares and palindromes. Based on his recent work [8, 9, 10, 12], Pongsriiam gave a talk on races between palindromes in different bases in a conference on algebra for young researchers, which led to the writing of this article. We obtain the intervals having minimal length that always contain a b-adic palindrome and a b-adic antipalindrome, respectively. The reader will see that the forms of some answers are connected to squares or square roots and look like analogs of Legendre’s conjecture on primes in short intervals; see for example in Corollaries 3, 17, and 21.

2 Main results

We split our main results into four subsections: (i) palindromes in short intervals, (ii) twin palindromes and fixed gaps between palindromes, (iii) antipalindromes of types 0, 1, and 2, and (iv) antipalindromes of type 3. We begin with palindromes as follows.

2.1 Palindromes in short intervals

Theorem 1. Let b be an integer not less than 2. Let c = \sqrt{b} + \sqrt{b^{−1}} and (x_{n}) the strictly increasing sequence of all b-adic palindromes. Then

x_{n+1} − x_{n} ≤ c\sqrt{x_{n} − 1} for all n ≥ 2,

and the inequality is sharp in the sense that there are infinitely many n ∈ ℕ such that

x_{n+1} − x_{n} = c\sqrt{x_{n} − 1}.  (1)

In fact, we obtain that (1) holds whenever x_{n} = b^{k} + 1, k ≥ 3, and k is odd.

Proof. Let n = (n_{k}n_{k−1} ⋯ n_{1}n_{0})_{b} be a b-adic palindrome with n ≥ 2 and n_{k} ≠ 0, and let m be the smallest b-adic palindrome larger than n. If 2 ≤ n < b − 1, then m = n + 1, and so m−n = 1 ≤ c\sqrt{n − 1}. If n = b−1, then b ≥ 3 and m = n+2, and so m−n = 2 ≤ c\sqrt{n − 1}. If b ≤ n ≤ b^{2}, then m = n+ℓ where ℓ = 2 or ℓ = b+1, and thus m−n ≤ b+1 = c\sqrt{b} ≤ c\sqrt{n − 1}. So assume throughout that n > b^{2}. Then k ≥ 2. If n = b^{k+1} − 1, then m − n = 2 ≤ c\sqrt{n − 1}. So assume that n ≠ b^{k+1} − 1. Then n_{i} ≠ b − 1 for some i = 0, 1, 2, …, k.

Case 1: k is odd and n_{\frac{k+1}{2}} ≠ b − 1. Let y = b^{\frac{k+1}{2}} + b^{\frac{k−1}{2}} . Then n + y is a b-adic palindrome, and so m ≤ n + y. This and n ≥ b^{k} + 1 imply that

\frac{m − n}{\sqrt{n − 1}} ≤ \frac{y}{\sqrt{n − 1}} ≤ \frac{b^{\frac{k+1}{2}} + b^{\frac{k−1}{2}}}{b^{\frac{k}{2}}} = c.

Case 2: k is even and n_{\frac{k}{2}} ≠ b − 1. Similar to Case 1, we obtain m ≤ n + b^{\frac{k}{2}} , and so (m − n)/\sqrt{n − 1} ≤ 1 ≤ c.

Case 3: k is odd and n_{\frac{k+1}{2}} = b − 1. Let i be the largest integer such that 0 ≤ i < \frac{k−1}{2} and n_{i} ≠ b − 1. Let y = b^{i+1} + b^{i}. Then n + y is a b-adic palindrome, and so

\frac{m − n}{\sqrt{n − 1}} ≤ \frac{y}{\sqrt{n − 1}} ≤ \frac{b^{\frac{k−1}{2}} + b^{\frac{k−3}{2}}}{b^{\frac{k}{2}}} = \frac{1}{\sqrt{b}} + \frac{1}{b\sqrt{b}} ≤ c.

Case 4: k is even and n_{\frac{k}{2}} = b − 1. Let i be the largest integer such that 0 ≤ i < \frac{k}{2} and n_{i} ≠ b − 1. Similar to Case 3, we obtain m ≤ n + b^{i+1} + b^{i} and

\frac{m − n}{\sqrt{n − 1}} ≤ 1 + \frac{1}{b} ≤ c.

In any case, we obtain m−n ≤ c\sqrt{n − 1}, which proves the first part of this theorem. Next, if n = b^{k} + 1 where k is an odd integer not less than 3, then m = n + b^{\frac{k+1}{2}} + b^{\frac{k−1}{2}} , and therefore

m − n = cb^{\frac{k}{2}} = c\sqrt{n − 1}.

This proves the second part. So the proof is complete.

Corollary 2. Let b be an integer not less than 2 and let (x_{n}) be the strictly increasing sequence of b-adic palindromes. Then

lim sup_{n→∞} \frac{x_{n+1} − x_{n}}{\sqrt{x_{n}}} = \sqrt{b} + \frac{1}{\sqrt{b}} and lim inf_{n→∞}(x_{n+1} − x_{n}) = 2.

Proof. The limit supremum follows immediately from Theorem 1. For the limit infimum, suppose y is the nonzero leading digit of x_{n}, and y_{0} is the last digit of x_{n} in the b-adic expansion of x_{n}, where x_{n} ≥ b. If y_{0} ≠ b − 1, then the last digit of x_{n} + 1 is y_{0} + 1 ≠ y, so x_{n} + 1 is not a b-adic palindrome. If y_{0} = b − 1, then the last digit of x_{n} + 1 is zero, so x_{n} + 1 cannot be a b-adic palindrome. This shows that if x_{n} ≥ b, then x_{n+1} ≥ x_{n} + 2. In addition, if x_{n} = b^{k} − 1 where k is a positive integer, then x_{n+1} = x_{n} + 2. So the limit infimum above is 2.

Corollary 3. Let b be an integer not less than 2 and let c = \sqrt{b} + \sqrt{b^{−1}}. Then for each integer n ≥ 2, there exists a b-adic palindrome in the interval

(n, n + c\sqrt{n − 1}] .

Furthermore, the interval is best possible in the sense that there are infinitely many n such that the open interval (n, n + c\sqrt{n − 1}) does not contain a b-adic palindrome.

Proof. Let n ≥ 2 and A = (n, n + c\sqrt{n − 1}]. If n is a b-adic palindrome, then the result follows immediately from Theorem 1. Suppose n is not a b-adic palindrome. Then we have

x_{m} < n < x_{m+1} where x_{m} and x_{m+1} are consecutive b-adic palindromes.

Then x_{m+1} > n and x_{m+1} ≤ x_{m} + c\sqrt{x_{m} − 1} < n + c\sqrt{n − 1}. So x_{m+1} ∈ A. If n = b^{k} + 1 and k is an odd integer not less than 3, then Theorem 1 implies that the open interval (n, n + c\sqrt{n − 1}) does not contain a b-adic palindrome.

The limit infimum in Corollary 2 leads us to the study of twin palindromes. If m > n, then we say that m and n are b-adic twin palindromes if m and n are b-adic palindromes and m = n + 2. In the next subsection, we determine all b-adic twin palindromes and give some related results.

2.2 Twin palindromes and fixed gaps between palindromes

Theorem 4. (Classification of all 2-adic twin palindromes) Let n be a 2-adic palindrome. Then n + 2 is a 2-adic palindrome if and only if n = 2^{k+1} − 1 for some integer k ≥ 0, or n = (101)_{2}.

Proof. It is clear that if n = (101)_{2} or n = 2^{k+1}−1 for some integer k ≥ 0, then n+2 is a 2-adic palindrome. Next, assume that m = n+2 is a 2-adic palindrome. Let n = (n_{k}n_{k−1} ⋯ n_{1}n_{0})_{b} and m = (m_{ℓ}m_{ℓ−1} ⋯ m_{1}m_{0})_{b} where k ≥ 0.

For 0 ≤ k ≤ 2, we see that the 2-adic palindromes having at most 3 digits are (1)_{2} = 2−1, (11)_{2} = 2^{2} − 1, (101)_{2}, and (111)_{2} = 2^{3} − 1, which are either (101)_{2} or of the form 2^{k+1} − 1 for some integer k ≥ 0. So we assume that k ≥ 3.

If n_{1} = 0, then we have k = ℓ, m_{1} = 1, n_{i} = m_{i} for all i ≠ 1, and so 1 = m_{1} = m_{k−1} = n_{k−1} = n_{1} = 0, a contradiction. Therefore n_{i} = 1 for all i ≤ 1. Let j be the largest integer less than or equal to ⌊k/2⌋ such that n_{i} = 1 for all i ≤ j. Suppose that j < ⌊k/2⌋. Then n_{j+1} = 0. Therefore m_{j+1} = 1, n_{i} = m_{i} for all i > j + 1, and m_{i} = 0 for all 1 ≤ i ≤ j. Then 0 = m_{1} = m_{k−1} = n_{k−1} = n_{1} = 1, a contradiction. Therefore j = ⌊k/2⌋. Then n_{i} = 1 for all i. Thus n = 2^{k+1} − 1.

Theorem 5. (Classification of all b-adic twin palindromes) Let b be an integer not less than 3 and let n be a b-adic palindrome not less than b. Then n + 2 is a b-adic palindrome if and only if n = b^{k+1} − 1 for some integer k ≥ 0.

Proof. It is clear that b^{k+1}+1 and b^{k+1}−1 are b-adic twin palindromes for every integer k ≥ 0. Next, let m and n be b-adic twin palindromes and m > n ≥ b. Let n = (n_{k}n_{k−1} ⋯ n_{1}n_{0})_{b} and m = (m_{ℓ}m_{ℓ−1} ⋯ m_{1}m_{0})_{b}, where k ≥ 1.

If n_{0} ≤ b − 3, then k = ℓ, n_{i} = m_{i} for all 1 ≤ i ≤ k, and m_{0} = n_{0} + 2. By the fact that n_{k} = n_{0}, n_{k} = m_{k}, and m_{k} = m_{0}, we have

m_{0} = n_{0} + 2 = n_{k} + 2 = m_{k} + 2 = m_{0} + 2,

which is not possible. If n_{0} = b − 2, then m_{ℓ} = m_{0} = 0, which is false. Therefore n_{0} = b − 1, and so m_{ℓ} = m_{0} = 1.

If ℓ = k, then 0 < n_{k} ≤ m_{ℓ} = 1. Thus 1 = n_{k} = n_{0} = b − 1, which is a contradiction. Thus we obtain ℓ = k + 1 and m_{k+1} = m_{0} = 1. Therefore n + 2 = m ≥ b^{k+1} + 1, and so b^{k+1} > n ≥ b^{k+1} − 1. Hence n = b^{k+1} − 1.

It is known that the sum of reciprocals of all twin primes converges, that is,

∑_{p and p + 2 are prime numbers} (\frac{1}{p} + \frac{1}{p + 2})  (2)

converges. This result was given by Brun [4], and the constant (2) is called Brun’s constant. It is unknown whether Brun’s constant is irrational or rational. If we obtained the irrationality of the constant, then we would conclude the infinitude of twin primes. We remark again that the mention of primes is only for the visual form of questions being asked. Instead of twin primes, we investigate the irrationality of the sum of reciprocals of all twin b-adic palindromes as follows:

Theorem 6. For each integer b ≥ 2, the sum of reciprocals of all b-adic twin palindromes converges to an irrational number, that is,

∑_{m and n are b-adic twin palindromes and m > n} (\frac{1}{n} + \frac{1}{m}) ∉ ℚ.  (3)

Proof. Fix b ≥ 2. By Theorems 4 and 5, it suffices to show that

∑_{k=1}^{∞} (\frac{1}{b^{k} − 1} + \frac{1}{b^{k} + 1}) = 2 ∑_{k=1}^{∞} \frac{b^{k}}{b^{2k} − 1}  (4)

is irrational. Define L(z) = ∑_{k=1}^{∞} z^{k}/(b^{2k} − 1) on |z| < b^{2}. Then we see that

L(z) − L (z/b^{2}) = ∑_{k=1}^{∞} \frac{z^{k} − (z/b^{2})^{k}}{b^{2k} − 1} = ∑_{k=1}^{∞} (\frac{z}{b^{2}} )^{k} = \frac{z}{b^{2} − z} .

Therefore we have

L(z) = \frac{z}{b^{2} − z} + L(z/b^{2})

= \frac{z}{b^{2} − z} + \frac{z}{b^{4} − z} + L(z/b^{4})

= ⋯ = ∑_{k=1}^{N} \frac{z}{b^{2k} − z} + L(z/b^{2N}).

Since lim_{N→∞} L(z/b^{2N}) = 0, we obtain L(z) = ∑_{k=1}^{∞} z/(b^{2k} − z). Substituting z = b in L(z), we see that the right-hand side of (4) is equal to 2 ∑_{k=1}^{∞} b/(b^{2k} − b). By Borwein’s result [3, Theorem 1], the sum ∑_{k=1}^{∞} 1/(b^{2k} − b) is irrational. Therefore (4) is irrational.

The irrationality of (4) is a direct consequence of Borwein’s result. Recall that the function

L_{q}(z) = ∑_{k=1}^{∞} \frac{z^{k}}{q^{k} − 1} = ∑_{k=1}^{∞} \frac{z}{q^{k} − z}

is called the q-logarithmic function. The irrationality and ℚ-linear independence of the special values of L_{q}(z) are well-studied. For example, by Tachiya’s result [14, Example 1], the following three numbers

1, L_{q}(1) = ∑_{k=1}^{∞} \frac{1}{q^{k} − 1}, L_{q}(−1) = − ∑_{k=1}^{∞} \frac{1}{q^{k} + 1}

are linearly independent over ℚ, which also immediately implies the irrationality of (4). We will use L_{q}(z) again in Conjecture 7 and Theorem 14.

We next investigate a more general setting. For all integers b ≥ 2 and d ≥ 1, we define

R(b; d) = {(n, m) ∈ ℕ^{2} | m and n are b-adic palindromes, and m − n = d},  (5)
C(b; d) = ∑_{(n,m)∈R(b;d)} (\frac{1}{n} + \frac{1}{m}) .

In view of the case d = 2, we expect the irrationality of C(b; d) for some other values of d ≥ 3 too. Nevertheless, not all C(b; d) are irrational. For instance, if R(b; d) is a finite set, then C(b; d) is rational. So we will first determine all values of d such that R(b; d) is an infinite set. Secondly, we describe all except a finite number of elements of R(b; d) when R(b; d) is infinite. After that we prove the irrationality of C(b; d) for all b and d such that R(b; d) is infinite by assuming Bundschuh and Väänänen’s conjecture [5].

Before stating the conjecture, we define K^{∗} = K \{0} to be the set of all nonzero elements of a field K, and q^{A} = {q^{a} | a ∈ A} for every A ⊆ ℝ. We also write L_{q}^{(n)}(z) for the nth derivative of L_{q}(z). Then Bundschuh and Väänänen’s conjecture is as follows.

Conjecture 7 ([5, Conjecture]). Let K be either ℚ or an imaginary quadratic number field, let q ∈ K be an integral element, and let z_{1}, …, z_{m} ∈ K^{∗} \ q^{ℕ} be such that z_{μ}/z_{μ′} ∉ q^{ℤ} for μ ≠ μ′. Then for each ℓ ∈ ℕ, the 1 + ℓm numbers

1, L_{q}(z_{1}), …, L_{q}(z_{m}), …, L_{q}^{(ℓ−1)}(z_{1}), …, L_{q}^{(ℓ−1)}(z_{m})  (6)

are linearly independent over K.

Remark 8. Note that L_{q}(z) − L_{q}(z′) ∈ K for all z, z′ ∈ K^{∗} \ q^{ℕ} with z/z′ ∈ q^{ℤ}. Indeed, for all z ∈ K and m ∈ ℤ, it follows that

L_{q}(zq^{m}) = ∑_{k=1}^{∞} \frac{zq^{m}}{q^{k} − zq^{m}} = ∑_{k=1}^{∞} \frac{z}{q^{k−m} − z} .

Therefore L_{q}(zq^{m}) − L_{q}(z) ∈ K.

We will apply Conjecture 7 with ℓ = 1 to give a conditional proof of the irrationality of C(b; d) for all suitable integers d ≥ 3, but before that we need some lemmas to obtain the values of d such that R(b; d) is infinite and describe its elements explicitly. Throughout Lemmas 9–11, we assume that n, m, and d are positive integers, m = n + d, and both m and n are b-adic palindromes. We also write n, m, and d as

n = (n_{k}n_{k−1} ⋯ n_{1}n_{0})_{b}, m = (m_{ℓ}m_{ℓ−1} ⋯ m_{1}m_{0})_{b}, and
d = (d_{r}d_{r−1} ⋯ d_{1}d_{0})_{b},  (7)

where k, ℓ, r ≥ 0, n_{k}, m_{ℓ}, d_{r} ≠ 0, and 0 ≤ n_{i}, m_{i}, d_{i} < b for all i.

Lemma 9. If 0 ≤ r ≤ (k − 1)/2, then n_{i} = b − 1 for all i ∈ [r, k − r]. The condition 0 ≤ r ≤ (k − 1)/2 is best possible in the sense that if k is even and r = k/2, then there are infinitely many n satisfying all of the other conclusions except for n_{k/2} = b − 1.

Proof. Let 0 ≤ r ≤ (k − 1)/2. We first show that

2b^{r+1} > (n_{r}n_{r−1} ⋯ n_{1}n_{0})_{b} + d ≥ b^{r+1}.  (8)

Since the two integers in the middle of (8) are less than b^{r+1}, the first inequality holds. Next, suppose that (n_{r}n_{r−1} ⋯ n_{1}n_{0})_{b} + d < b^{r+1}. Then k = ℓ, m_{i} = n_{i} for all i ∈ (r, k], and

(m_{r}m_{r−1} ⋯ m_{1}m_{0})_{b} = (n_{r}n_{r−1} ⋯ n_{1}n_{0})_{b} + d.  (9)

By (9), we see that m_{j} ≠ n_{j} for some j ∈ [0, r], and therefore m_{k−j} = n_{k−j} = n_{j} ≠ m_{j}, which contradicts the assumption that m is a b-adic palindrome. So the second inequality in (8) is proved.

We next show that

n_{i} = b − 1 for all i ∈ (r, k − r).  (10)

We note that if r ≤ (k − 2)/2, then the interval (r, k − r) is not empty and we need to prove that (10) holds. If r = (k −1)/2, then (r, k −r)∩ℤ = ∅; in this case, we can skip the proof of (10) and proceed to the proof of (11). So in the proof of (10), we assume that r ≤ (k − 2)/2.

Suppose n_{i} ≠ b − 1 for some i ∈ (r, ⌈\frac{k}{2}⌉). Let j be the smallest integer in (r, ⌈\frac{k}{2}⌉) such that n_{j} ≠ b − 1. Then n_{i} = b − 1 for i ∈ (r, j), and by (8), we also obtain m_{j} = n_{j} + 1, k = ℓ, and m_{i} = n_{i} for all i ∈ (j, k]. Therefore n_{j} + 1 = m_{j} = m_{k−j} = n_{k−j} = n_{j}, which is a contradiction. Thus n_{i} = b − 1 for all i ∈ (r, ⌈\frac{k}{2}⌉). Since n is a palindrome, we obtain that n_{k−i} = n_{i} = b − 1 for all i ∈ (r, ⌈\frac{k}{2}⌉). So, if k is odd, then (10) is proved. If k is even, then n_{i} = b − 1 for all i ∈ (r, k − r) \ \{\frac{k}{2}\}, and it remains to show that n_{\frac{k}{2}} = b − 1. So let k be even and suppose that n_{\frac{k}{2}} ≠ b − 1. Then by (8), we obtain m_{\frac{k}{2}} = n_{\frac{k}{2}} + 1, k = ℓ, m_{i} = n_{i} for all i ∈ (\frac{k}{2}, k], and m_{i} = 0 for all i ∈ (r, \frac{k}{2}). If r ≤ \frac{k}{2} − 2, then 0 = m_{\frac{k}{2} −1} = m_{\frac{k}{2} +1} = n_{\frac{k}{2} +1} = n_{\frac{k}{2} −1} = b − 1, a contradiction. So r = \frac{k}{2} − 1. Since m_{i} = n_{i} for all i ∈ (\frac{k}{2}, k], we obtain that m_{i} = m_{k−i} = n_{k−i} = n_{i} for all i ∈ [0, r]. Therefore m_{i} = n_{i} for all i ≠ \frac{k}{2} and m_{\frac{k}{2}} = n_{\frac{k}{2}} + 1. Thus b^{\frac{k}{2}} = b^{r+1} > d = m − n = b^{\frac{k}{2}} , which is not possible. Hence n_{\frac{k}{2}} = b − 1 and (10) is proved.

The remaining part of the proof is to show

n_{r} = n_{k−r} = b − 1.  (11)

Suppose that n_{k−r} < b − 1. By (8) and (10), it follows that k = ℓ, m_{k−r} = n_{k−r} + 1, and m_{r} = d_{r} + n_{r} + i − b, where i = 0 or 1. Therefore

d_{r} + n_{r} + i − b = m_{r} = m_{k−r} = n_{k−r} + 1 = n_{r} + 1 ≥ n_{r} + i,

and so d_{r} ≥ b, which is a contradiction. Hence n_{r} = n_{k−r} = b − 1 and the proof of the first part is complete. For the second part, let k be an even integer not less than 2, r = k/2, d = b^{k/2}, n = ∑_{0≤i≤k} n_{i}b^{i}, where n_{k} ≠ 0, n_{k/2} ∈ [0, b − 2], n_{i} ∈ [0, b), n_{i} = n_{k−i} for all i ∈ [0, k], and m = n + d. Then m and n are b-adic palindromes and n_{k/2} ≠ b − 1. Since k is arbitrary, there are infinitely many such n, and the second part of this lemma is proved.

We remark that the example given in the second part of the proof of Lemma 9 was also used in the construction of the longest arithmetic progressions of palindromes in base b = 10 by Pongsriiam [11]. It will be used again in a forthcoming article of Phunphayap and Pongsriiam on longest arithmetic progressions of b-adic palindromes for all large b. So the optimal bound 0 ≤ r ≤ (k − 1)/2 in Lemma 9 may not be necessary in this paper, but it will be useful in the future. Similarly, Lemma 10 is given in an optimal form as follows.

Lemma 10. If 0 ≤ r ≤ k/2 and n_{i} = b−1 for all i ∈ [0, k], then d = 2. If k is odd, r = \frac{k+1}{2}, and n_{i} = b − 1 for all i ∈ [0, k], then d ≥ 2 and if d ≠ 2, then the smallest possible value of d is d = 2 + b^{\frac{k+1}{2}} . In particular, the bound 0 ≤ r ≤ k/2 in the first statement is optimal.

Proof. For the first statement, assume that 0 ≤ r ≤ k/2 and n_{i} = b − 1 for all i ∈ [0, k]. Then n = b^{k+1} − 1. By m = n + d = b^{k+1} + (d − 1) and 0 ≤ d − 1 < b^{r+1}, we have ℓ = k + 1, m_{k+1} = 1, and m_{i} = 0 for all i ∈ (r, k]. Since m is a b-adic palindrome, we have m_{0} = 1. Since m is a b-adic palindrome, we conclude that m_{i} = 0 for all i ∈ [1, k]. Hence m = b^{k+1} + 1. Therefore

d = m − n = (b^{k+1} + 1) − (b^{k+1} − 1) = 2,

as required. Next, let k be odd, r = \frac{k+1}{2}, and n_{i} = b − 1 for all i ∈ [0, k]. Then n = b^{k+1} − 1 and it is obvious that n + 1 is not a b-adic palindrome. So d ≥ 2. So assume that d ≠ 2. Then m > b^{k+1} + 1 and the smallest b-adic palindrome larger than b^{k+1} + 1 is b^{k+1} + 1 + b^{\frac{k+1}{2}} . Therefore the smallest value of d is

d = (b^{k+1} + 1 + b^{\frac{k+1}{2}} ) − (b^{k+1} − 1) = 2 + b^{\frac{k+1}{2}} .

This completes the proof.

After we have Lemma 9, we can split our consideration into two cases. The first case is that n_{i} = b−1 for all i ∈ [0, r), which leads to Lemma 10. The second case is that n_{j} ≠ b−1 for some j ∈ [0, r) which is considered in the next lemma as follows.

Lemma 11. Let 1 ≤ r ≤ (k − 1)/2 and let j be the largest integer in the interval [0, r) such that n_{j} < b − 1. Then j = r − 1 and d = b^{r} + b^{r−1}. Furthermore, if b = 2, then r ≥ 2.

Proof. We first note that since n_{k−j} = n_{j} < b−1 and j ≤ r−1, we have n ≤ b^{k+1}−1−b^{k−j} ≤ b^{k+1} − 1 − b^{k−r+1} and so

m = n + d ≤ b^{k+1} − 1 − b^{k−r+1} + b^{r+1} < b^{k+1}.

Therefore ℓ = k. Next, we suppose by way of contradiction that j < r − 1. The choice of j implies that n_{i} = b − 1 for all i ∈ (j, r). By applying Lemma 9, we also have n_{i} = b − 1 for all i ∈ [r, k − r]. Since n is a b-adic palindrome, we obtain n_{i} = b − 1 for all i ∈ (j, k − j). We assert that

(n_{j} ⋯ n_{0})_{b} + (d_{j} ⋯ d_{0})_{b} < b^{j+1}.  (12)

If (12) does not hold, then it follows that m_{i} = d_{i} for all i ∈ (j, r], m_{i} = 0 for all i ∈ (r, k−j), and m_{k−j} = n_{k−j} + 1, which implies 0 = m_{k−r} = m_{r} = d_{r}, a contradiction. Thus (12) holds. Similarly, if there exists an integer i ∈ (j, r) such that d_{i} > 0, then we obtain 0 = m_{k−r} = m_{r} = d_{r}, which is not possible. Therefore d_{i} = 0 for all i ∈ (j, r).

Combining the above discussion, we have

d_{i} = 0 for j < i < r,  (13)
(m_{j} ⋯ m_{0})_{b} = (n_{j} ⋯ n_{0})_{b} + (d_{j} ⋯ d_{0})_{b} < b^{j+1},  (14)
ℓ = k, m_{i} = n_{i} for k − j < i ≤ k, m_{k−j} = n_{k−j} + 1,  (15)
m_{i} = 0 for r < i < k − j, m_{r} = d_{r} − 1,  (16)
m_{i} = b − 1 for j < i < r.  (17)

Recall that j + 1 < r. So we can substitute i = k − j − 1 in (16) and i = j + 1 in (17) to obtain 0 = m_{k−j−1} = m_{j+1} = b − 1, which is a contradiction. Therefore j = r − 1. Then (14), (15), and (16) can be rewritten as

(m_{r−1} ⋯ m_{0})_{b} = (n_{r−1} ⋯ n_{0})_{b} + (d_{r−1} ⋯ d_{0})_{b} < b^{r},  (18)
ℓ = k, m_{i} = n_{i} for k − r + 1 < i ≤ k, m_{k−r+1} = n_{k−r+1} + 1,  (19)
m_{i} = 0 for r < i ≤ k − r, m_{r} = d_{r} − 1.  (20)

Then (20) implies that 0 = m_{k−r} = m_{r} = d_{r} − 1, and so d_{r} = 1. Next, we assert that

d_{i} = 0 for every i ∈ [0, r − 1).  (21)

Suppose that (21) does not hold. Let j′ be the smallest integer in the interval [0, r − 1) such that d_{j′} ≠ 0. Then we substitute i = k − j′ in (19) to obtain m_{k−j′} = n_{k−j′}. In addition, since d_{i} = 0 for all i ∈ [0, j′), we obtain that m_{j′} = n_{j′} + d_{j′} or m_{j′} = n_{j′} + d_{j′} − b. Therefore

n_{j′} = n_{k−j′} = m_{k−j′} = m_{j′} ≡ n_{j′} + d_{j′} (mod b),

which implies d_{j′} = 0 contradicting the choice of j′. Hence (21) holds. Then (19), (18), and (21) imply that n_{k−r+1} + 1 = m_{k−r+1} = m_{r−1} = n_{r−1} + d_{r−1} = n_{k−r+1} + d_{r−1}, and hence d_{r−1} = 1. Therefore d = b^{r} + b^{r−1}.

In the case b = 2 and r = 1, we see that d = (11)_{2} and m_{0} ∈ {0, 1}. However, it is easy to see that m_{0} = 0 implies m_{k} = m_{0} = 0, and m_{0} = 1 implies n_{k} = n_{0} = 0, which is a contradiction. Thus, if b = 2, then r ≥ 2. This completes the proof.

We are now ready to give the proof of the desired results. In the statement of the next theorem, we call a pair (r, b) of integers admissible if (r, b) satisfies that r ≥ 2 if b = 2, and r ≥ 1 otherwise. For every admissible pair (r, b), we find the explicit forms of all except a finite number of elements of R(b; d) as follows.

Theorem 12. Let b and d be integers, b ≥ 2, and d ≥ 1. Then the following statements hold.

(i) If b = 2, then R(b; d) is infinite if and only if d = 2 or d = 2^{r} + 2^{r−1} for some r ≥ 2.

(ii) If b ≥ 3, then R(b; d) is infinite if and only if d = 2 or d = b^{r} + b^{r−1} for some r ≥ 1.

(iii) For every admissible pair (r, b), there exists an exceptional finite set E = E(r, b) ⊆ ℕ^{2} such that (n, m) ∈ R(b; b^{r} + b^{r−1}) \ E if and only if

n = ∑_{0≤i<r} n_{i}b^{k−i} + (b − 1) ∑_{r≤i≤k−r} b^{i} + ∑_{0≤i<r} n_{i}b^{i}, and  (22)
m = n + b^{r} + b^{r−1}

for some integers k ≥ 2r + 1, n_{0} ∈ [1, b), n_{r−1} ∈ [0, b − 1), and n_{i} ∈ [0, b) for all i ∈ (0, r − 1).

Remark 13. If r = 1, then (22) in Theorem 12 means that b ≥ 3, k ≥ 3, 1 ≤ n_{0} < b − 1, and

n = n_{0}b^{k} + (b − 1) ∑_{1≤i≤k−1} b^{i} + n_{0},

and therefore n + b^{r} + b^{r−1} = (n_{0} + 1)b^{k} + (n_{0} + 1). If r ≥ 2 and n is defined as in (22), then

n + b^{r} + b^{r−1} = ∑_{0≤i<r−1} n_{i}b^{k−i} + (n_{r−1} + 1)b^{k−r+1} + (n_{r−1} + 1)b^{r−1}

+ ∑_{0≤i<r−1} n_{i}b^{i}

= ∑_{0≤i<r} n_{i}b^{k−i} + b^{k−r+1} + b^{r−1} + ∑_{0≤i<r} n_{i}b^{i}.

In addition, we can also rewrite (22) as

n = ∑_{0≤i<r} n_{i}b^{k−i} + b^{k−r+1} − b^{r} + ∑_{0≤i<r} n_{i}b^{i}.  (23)

We use the form (22) in the proof of Theorem 12 and use both (22) and (23) in the proof of Theorem 14.

Proof of Theorem 12. It is easy to see that (b^{k} − 1, b^{k} + 1) ∈ R(b; 2) for all k ∈ ℕ, and so R(b; d) is infinite when d = 2. Next, let r ≥ 2 and d = b^{r} + b^{r−1}. Let n be defined as in (22) and let m = n + d. Then it is not difficult to check that (n, m) ∈ R(b; d). Since k is an arbitrary integer not less than 2r + 1, there are infinitely many n satisfying (22). Therefore R(b; d) is infinite. In the case b ≥ 3 and r = 1, the above proof still works. So the “if” parts of (i) and (ii) are proved. In addition, the set

E = E(r, b) = {(n′, m′) ∈ ℕ^{2} | n′ < b^{2r+1} and m′ = n′ + d}  (24)

is finite and does not contain (n, m). So (n, m) ∈ R(b; d) \ E. This proves the “if” part of (iii).

Next, assume that R(b; d) is infinite. Let E be defined as in (24). Then E is finite, and so R(b; d) \ E is infinite. Let (n, m) ∈ R(b; d) \ E. Then n and m are b-adic palindromes, m = n + d, and n ≥ b^{2r+1}. We write n, m, and d as in (7). Then 0 ≤ r ≤ (k − 1)/2. By Lemma 9, we obtain n_{i} = b − 1 for all i ∈ [r, k − r]. If r = 0, then this means that n_{i} = b − 1 for all i ∈ [0, k], and we can apply Lemma 10 to obtain d = 2, which proves the “only if” parts of (i) and (ii). If n_{i} = b − 1 for all i ∈ [0, r), then this also leads to Lemma 10 and the conclusion that d = 2. So assume that r ≥ 1 and j is the largest integer in [0, r) such that n_{j} < b − 1. Then Lemma 11 implies the “only if” parts of (i) and (ii).

So it remains to prove the “only if” part of (iii). We now have (n, m) in R(b; d) \ E where d = b^{r} + b^{r−1}, r ∈ ℕ, and r ≥ 2 if b = 2. We also have k ≥ 2r + 1, n_{i} = b − 1 for all i ∈ [r, k − r], n_{j} = n_{r−1} < b − 1. Since n is a b-adic palindrome, we have n_{0} ≠ 0. Therefore n_{0} ∈ [1, b), n_{r−1} ∈ [0, b − 1), n_{i} ∈ [0, b) for all i ∈ [0, k], and n_{i} = n_{k−i} for all i ∈ [0, k]. Hence n is of the form (22). This proves the “only if” part of (iii) and so the proof is complete.

Theorem 14. Assume that Conjecture 7 with ℓ = 1 is true. Then for every admissible pair (r, b), the constant C(b; b^{r} + b^{r−1}) is irrational.

Proof. Fix an admissible pair (r, b). For n = (n_{k}n_{k−1} ⋯ n_{r} ⋯ n_{0})_{b} with n_{0} ∈ [1, b), n_{r−1} ∈ [0, b − 1), and n_{i} ∈ [0, b) for all i ∈ (0, r − 1), we define

Q = Q(n) = Q(n_{0}, …, n_{r}, …, n_{k}) = b^{r} + ∑_{0≤i<r} n_{i}b^{2r−1−i},
P_{0} = P_{0}(n) = P_{0}(n_{0}, …, n_{r}, …, n_{k}) = b^{r} − ∑_{0≤i<r} n_{i}b^{i},
P_{1} = P_{1}(n) = P_{1}(n_{0}, …, n_{r}, …, n_{k}) = −b^{r−1} − ∑_{0≤i<r} n_{i}b^{i}.

By Theorem 12, the constant C(b; b^{r} + b^{r−1}) is irrational if and only if the sum

∑_{n} (\frac{1}{n} + \frac{1}{n + b^{r} + b^{r−1}} ) = ∑_{n_{0},n_{1},...,n_{r−1}} ∑_{k=2r+1}^{∞} (\frac{1}{n} + \frac{1}{n + b^{r} + b^{r−1}} )  (25)

is irrational, where n ranges over all positive integers of the form (22) satisfying that n_{0} ∈ [1, b), n_{r−1} ∈ [0, b − 1), and n_{i} ∈ [0, b) for all i ∈ (0, r − 1). By adding the finite number of terms with k = 2r, we can replace ∑_{k=2r+1}^{∞} with ∑_{k=2r}^{∞} in (25) and obtain that C(b; b^{r}+b^{r−1}) is irrational if and only if

∑_{n_{0},n_{1},...,n_{r−1}} ∑_{k=2r}^{∞} (\frac{1}{n} + \frac{1}{n + b^{r} + b^{r−1}} )

= ∑_{n_{0},n_{1},...,n_{r−1}} (∑_{k=1}^{∞} \frac{1}{Qb^{k} − P_{0}} + ∑_{k=1}^{∞} \frac{1}{Qb^{k} − P_{1}} )

= ∑_{n_{0},n_{1},...,n_{r−1}} \frac{L_{b}(P_{0}/Q)}{P_{0}} + ∑_{n_{0},n_{1},...,n_{r−1}} \frac{L_{b}(P_{1}/Q)}{P_{1}}  (26)

is irrational. We remark that P_{i}/Q ≠ b^{k} for all k ≥ 1 and i ∈ {0, 1}. Let S_{0} and S_{1} be the first and second sums in (26), respectively. For each i ∈ {0, 1} and n ∈ ℕ, we define z_{n}^{(i)} = P_{i}(n)/Q(n). The sign of each P_{i} is (−1)^{i} by the definition of P_{i}. So we have z_{n}^{(0)} > 0 and z_{n}^{(1)} < 0 for all n. By Remark 8 and combining terms L_{b}(z_{n}^{(i)}) and L_{b}(z_{n′}^{(i)}) in S_{i} satisfying z_{n}^{(i)}/z_{n′}^{(i)} ∈ b^{ℤ}, the sum S_{i} can be rewritten as

B^{(i)} + ∑_{n} A_{n}^{(i)}L_{b}(z_{n}^{(i)}),

where the sum is taken over all a finite number of n, B^{(i)} ∈ ℚ, A_{n}^{(i)} ∈ ℚ^{∗}, (−1)^{i}A_{n}^{(i)} > 0, z_{n}^{(i)} ∈ ℚ^{∗} \ b^{ℕ}, (−1)^{i}z_{n}^{(i)} > 0, and z_{n}^{(i)}/z_{n′}^{(i)} ∉ b^{ℤ} for n ≠ n′. Therefore (26) is equal to

B^{(0)} + B^{(1)} + ∑_{n} A_{n}^{(0)}L_{b}(z_{n}^{(0)}) + ∑_{n} A_{n}^{(1)}L_{b}(z_{n}^{(1)}).

We remark that z_{n}^{(1)}/z_{n′}^{(0)} < 0 implies z_{n}^{(1)}/z_{n′}^{(0)} ∉ b^{ℤ}. Hence, Conjecture 7 with ℓ = 1 implies the irrationality of (26).

In the next subsection, we first give a lemma which is a key to the construction of large gaps between b-adic antipalindromes of types 0, 1, and 2.

2.3 Antipalindromes of types 0, 1, and 2 in short intervals

From this point on, for each n ∈ ℕ and j = 0, 1, 2, we let f_{j}(n) be the smallest b-adic antipalindrome of type j that is larger than n.

Lemma 15. Let b and k be integers larger than 1. Then the following statements hold.

(i) For each j ∈ {0, 1, 2}, the b-adic antipalindromes of type j are uniquely determined by their first half digits. More precisely, if y = ∑_{i=0}^{k} y_{i}b^{i} and n = ∑_{i=0}^{k} n_{i}b^{i} are b-adic antipalindromes of the same type j ∈ {0, 1, 2} and y_{i} = n_{i} for each i ≥ ⌈k/2⌉, then y = n.

(ii) For each j ∈ {0, 1}, if n is a b-adic antipalindrome of type j, then n is a b-adic antipalindrome of type j + 1.

(iii) For each n ∈ ℕ, we have f_{0}(n) ≥ f_{1}(n) ≥ f_{2}(n).

(iv) If n = b^{k}, then f_{2}(n) = b^{k} + b^{⌈^{\frac{k}{2}}⌉} − 2.

(v) If n = b^{k+1} − b^{⌈^{\frac{k}{2}}⌉}, then f_{2}(n) = b^{k+1} + b^{⌈^{\frac{k+1}{2}}⌉} − 2.

(vi) If n = b^{k} + b^{k−j} − b^{\frac{k+1}{2}} + b^{j+1} − 2 where k ≥ 11, k is odd, and j = ⌊k/3⌋, then f_{2}(n) = b^{k} + b^{k−j} + b^{\frac{k+1}{2}} − b^{j} − 2.

(vii) If n = b^{k} + b^{k−j} − b^{\frac{k}{2} +1} + (\frac{b−1}{2}) b^{\frac{k}{2}} + b^{j+1} − 2 where k ≥ 10, k is even, and j = ⌊k/3⌋, then f_{1}(n) = b^{k} + b^{k−j} + (\frac{b+1}{2}) b^{\frac{k}{2}} − b^{j} − 2.

Proof. The statements (i) to (iii) are obvious, so we skip the proof. Next, we prove (iv). Let

n = b^{k} = (n_{k}n_{k−1} ⋯ n_{0})_{b} and m = b^{k} + b^{⌈^{\frac{k}{2}}⌉} − 2 = (m_{k}m_{k−1} ⋯ m_{0})_{b},

where n_{k} = 1, n_{i} = 0 for all i < k, m_{k} = 1, m_{i} = 0 for ⌈k/2⌉ ≤ i < k, m_{i} = b − 1 for 0 < i < ⌈k/2⌉, and m_{0} = b − 2. It is straightforward to check that m is a b-adic antipalindrome of type 2 larger than n. Suppose that y is a b-adic antipalindrome of type 2 satisfying n < y ≤ m. By comparing the digits of n, y, m, we see that y_{i} = m_{i} for all i ≥ ⌈k/2⌉. Therefore we obtain by (i) that y = m. This shows that f_{2}(n) = m.

Next, let n = b^{k+1} − b^{⌈^{\frac{k}{2}}⌉} = (n_{k}n_{k−1} ⋯ n_{0})_{b} where n_{i} = b − 1 for i ≥ ⌈k/2⌉ and n_{i} = 0 for i < ⌈k/2⌉. Let m = b^{k+1} + b^{⌈^{\frac{k+1}{2}}⌉} − 2 and let y be a b-adic antipalindrome of type 2 satisfying n < y ≤ m. If n < y < b^{k+1}, then y = (y_{k} ⋯ y_{0})_{b} where y_{i} = b − 1 for i ≥ ⌈k/2⌉ and y_{j} > 0 for some j < ⌈k/2⌉, which implies that y is not a b-adic antipalindrome of type 2, a contradiction. So b^{k+1} ≤ y ≤ m. Then the first half digits of y and m are the same. So we obtain by (i) that y = m. This shows that f_{2}(n) = m.

Next, let n be defined as in (vi). Then

n = b^{k} + (b − 1) ∑_{\frac{k+1}{2} ≤i≤k−j−1} b^{i} + (b − 1) ∑_{1≤i≤j} b^{i} + (b − 2) = (n_{k}n_{k−1} ⋯ n_{0})_{b},

where n_{k} = 1, n_{i} = b − 1 for i ∈ [1, j] ∪ [\frac{k+1}{2}, k − j − 1], n_{0} = b − 2, and n_{i} = 0 otherwise. Let y be the smallest b-adic antipalindrome larger than n. By comparing the digits as in the proof of (iv) and (v), we see that if

n < y < b^{k} + b^{k−j},

then y is not a b-adic antipalindrome. Therefore

y ≥ b^{k} + b^{k−j}.

Let m = b^{k} +b^{k−j} +b^{\frac{k+1}{2}} −b^{j} −2 = (m_{k}m_{k−1} ⋯ m_{0})_{b} where m_{k} = m_{k−j} = 1, m_{j} = m_{0} = b−2, m_{i} = b − 1 for i ∈ (0, j) ∪ (j, \frac{k+1}{2}), and m_{i} = 0 otherwise. Then m is a b-adic antipalindrome larger than n. Therefore b^{k} + b^{k−j} ≤ y ≤ m. By comparing the digits of b^{k} + b^{k−j}, m, y, and applying (i), we obtain that f_{2}(n) = y = m.

Next, let n be defined as in (vii). The proof of (vii) is similar to (vi), so we skip some details. We have

n = b^{k} + (b − 1) ∑_{\frac{k}{2} <i<k−j} b^{i} + (\frac{b − 1}{2}) b^{\frac{k}{2}} + (b − 1) ∑_{1≤i≤j} b^{i} + (b − 2).

By comparing the digits, we see that there is no b-adic antipalindromes that lie in the interval (n, n + y] where y = b^{\frac{k}{2}} − b^{j+1} + 1. In addition, the integers in the interval [n + y + 1, b^{k} + b^{k−j} + (\frac{b−1}{2}) b^{\frac{k}{2}} ) are not b-adic antipalindromes since their middle digits

(the digit corresponding to b^{\frac{k}{2}} ) are not \frac{b−1}{2}. Therefore f_{1}(n) ≥ b^{k} + b^{k−j} + (\frac{b−1}{2}) b^{\frac{k}{2}} . Let m = b^{k} +b^{k−j} +(\frac{b+1}{2}) b^{\frac{k}{2}} −b^{j} −2. Then m is a b-adic antipalindrome larger than n. Therefore

b^{k} + b^{k−j} + (\frac{b − 1}{2}) b^{\frac{k}{2}} ≤ f_{1}(n) ≤ m.

By comparing the digits and applying (i), we obtain f_{1}(n) = m, as required. This completes the proof.

Theorem 16. Let b be an integer not less than 2 and (x_{n}) the strictly increasing sequence of b-adic antipalindromes of type 2 (free middle type). Then

x_{n+1} − x_{n} ≤ 2\sqrt{b}\sqrt{x_{n}} for all n ∈ ℕ,  (27)

and (27) is sharp in the sense that

lim sup_{n→∞} \frac{x_{n+1} − x_{n}}{\sqrt{x_{n}}} = 2\sqrt{b}.

Proof. Throughout the proof, all b-adic antipalindromes are of type 2. Let n be a b-adic antipalindrome, and write n = (n_{k}n_{k−1} ⋯ n_{0})_{b} with n_{k} ≠ 0. Let m = f_{2}(n). If 1 ≤ n < b−1, then m = n + 1 and so m − n < 2\sqrt{b}\sqrt{n}. It is easy to see that b, b + 1, …, b + (b − 3) are not b-adic antipalindromes, but b + (b − 2) is. So if n = b − 1, then m = 2n, and so m−n < 2\sqrt{b}\sqrt{n}. By listing all b-adic antipalindromes in [b, b^{3}], it is straightforward to check that if b ≤ n < b^{3}, then m − n ≤ 2b − 2 < 2\sqrt{b}\sqrt{n}. So we assume that n ≥ b^{3}. Therefore k ≥ 3. Next, we split the calculations into 6 cases.

Case 1: k is odd and n_{\frac{k+1}{2}} ≠ b − 1. Then n_{\frac{k−1}{2}} ≥ 1. Let y = b^{\frac{k+1}{2}} − b^{\frac{k−1}{2}} = (b − 1)b^{\frac{k−1}{2}} . Then n + y is a b-adic antipalindrome, and so m ≤ n + y. Therefore

\frac{m − n}{\sqrt{n}} ≤ \frac{y}{\sqrt{n}} ≤ \frac{b^{\frac{k+1}{2}} − b^{\frac{k−1}{2}}}{\sqrt{b^{k}}} = \sqrt{b} − \sqrt{b^{−1}},

which is less than 2\sqrt{b}. Case 2: k is even and n_{\frac{k}{2}} ≠ b − 1. Then n + b^{\frac{k}{2}} is a b-adic antipalindrome. Therefore m − n ≤ b^{\frac{k}{2}} < \sqrt{n} < 2\sqrt{b}\sqrt{n}. Case 3: k is even and n_{i} = b − 1 for all i ≥ k/2. Then n_{i} = 0 for all i < k/2, and so n = b^{k+1} − b^{\frac{k}{2}} . By Lemma 15, we obtain m = b^{k+1} + b^{\frac{k+2}{2}} − 2. If b ≥ 3, then

\frac{m − n}{\sqrt{n}} < \frac{b^{\frac{k+2}{2}} + b^{\frac{k}{2}}}{\sqrt{b^{k+1} − b^{\frac{k}{2}}}} < \frac{b^{\frac{k+2}{2}} + b^{\frac{k}{2}}}{\sqrt{b^{k+1}/2}} = \sqrt{2} (\sqrt{b} + \sqrt{b^{−1}}) < 2\sqrt{b}.

Since k ≥ 3 and k is even, we have k ≥ 4. So if b = 2, then

\frac{m − n}{\sqrt{n}} < \frac{2^{\frac{k+2}{2}} + 2^{\frac{k}{2}}}{\sqrt{2^{k+1} − 2^{\frac{k}{2}}}} = \frac{\sqrt{2} + \sqrt{2^{−1}}}{\sqrt{1 − 2^{−(k+2)/2}}} ≤ \frac{\sqrt{2} + \sqrt{2^{−1}}}{\sqrt{7/8}} < 2\sqrt{2}.

So, in any case, we have m − n < 2\sqrt{b}\sqrt{n}. Case 4: k is even, n_{\frac{k}{2}} = b − 1, and n_{i} ≠ b − 1 for some i > k/2. Then n_{i} ≠ 0 for some i < k/2. Let j be the largest integer less than \frac{k}{2} such that n_{j} ≠ 0. Then n_{k−j} ≠ b − 1. Let

y = 2b^{\frac{k}{2}} − b^{j+1} − b^{j} = b^{\frac{k}{2}} + (b − 1) ∑_{j<i< \frac{k}{2}} b^{i} − b^{j}.

Then n + y is a b-adic antipalindrome, and so m − n ≤ y < 2b^{\frac{k}{2}} < 2\sqrt{n} < 2\sqrt{b}\sqrt{n}. Case 5: k is odd and n_{i} = b − 1 for all i ≥ \frac{k+1}{2}. Then n_{i} = 0 for all i ≤ \frac{k−1}{2} and so n = b^{k+1} − b^{\frac{k+1}{2}} . By Lemma 15, we obtain m = b^{k+1} + b^{\frac{k+1}{2}} − 2. Therefore

m − n < 2b^{\frac{k+1}{2}} = 2\sqrt{b} · b^{\frac{k}{2}} < 2\sqrt{b}\sqrt{n}.

Case 6: k is odd, n_{\frac{k+1}{2}} = b − 1, and n_{i} ≠ b − 1 for some i > \frac{k+1}{2}. Then n_{i} ≠ 0 for some i < \frac{k−1}{2}. Let j be the largest integer less than \frac{k−1}{2} such that n_{j} ≠ 0. Then n_{k−j} ≠ b − 1. Let

y = 2b^{\frac{k+1}{2}} − b^{j+1} − b^{j} = b^{\frac{k+1}{2}} + (b − 1) ∑_{j<i< \frac{k+1}{2}} b^{i} − b^{j}.

Then n + y is a b-adic antipalindrome. Therefore

m − n ≤ y < 2b^{\frac{k+1}{2}} = 2\sqrt{b} · b^{\frac{k}{2}} < 2\sqrt{b}\sqrt{n}.

From Cases 1–6, we conclude that x_{n+1} − x_{n} ≤ 2\sqrt{b}\sqrt{x_{n}} for all n ≥ 1.

For the limit supremum, we construct a specific n similar to Case 6 where k ≥ 11, k is odd, and j = ⌊k/3⌋. That is, we let

n = b^{k} + (b − 1) ∑_{\frac{k+1}{2} ≤i≤k−j−1} b^{i} + (b − 1) ∑_{1≤i≤j} b^{i} + (b − 2)

= b^{k} + b^{k−j} − b^{\frac{k+1}{2}} + b^{j+1} − 2,

where k ≥ 11, k is odd, and j = ⌊k/3⌋. By Lemma 15, we obtain

m = b^{k} + b^{k−j} + b^{\frac{k+1}{2}} − b^{j} − 2.

Therefore

\frac{m − n}{\sqrt{n}} = \frac{2b^{\frac{k+1}{2}} − b^{j+1} − b^{j}}{\sqrt{n}} = \frac{2\sqrt{b} − b^{j+1− \frac{k}{2}} − b^{j− \frac{k}{2}}}{\sqrt{1 + b^{−j} − b^{\frac{1−k}{2}} + b^{j+1−k} − 2b^{−k}}} ,

which converges to 2\sqrt{b} as k → ∞. Therefore (m − n)/\sqrt{n} converges to 2\sqrt{b} as n → ∞. This proves

lim sup_{n→∞} \frac{x_{n+1} − x_{n}}{\sqrt{x_{n}}} = 2\sqrt{b},

as required. So the proof is complete.

Corollary 17. Let b be an integer not less than 2 and c = 2\sqrt{b}. Then for each n ∈ ℕ, the interval (n, n + c\sqrt{n}] always contains a b-adic antipalindrome of type 2 (free middle type). This is best possible in the sense that if ε > 0 is given, then there are infinitely many n ∈ ℕ such that the interval (n, n + (c − ε)\sqrt{n}] does not contain a b-adic antipalindrome of type 2.

Proof. We apply Theorem 16 and an argument similar to Corollary 3 to obtain this corollary.

Theorem 18. Let b be an integer not less than 2 and (x_{n}) the strictly increasing sequence of b-adic antipalindromes of type 0 (no middle type). Then x_{n+1} − x_{n} < c_{n}(b − 1)x_{n} for all n ∈ ℕ, where

c_{n} = 1 + \frac{2b}{(b − 1) (\sqrt{n + 1} − 1)}.  (28)

In addition, we have

lim sup_{n→∞} \frac{x_{n+1} − x_{n}}{x_{n}} = b − 1.

Proof. Since type 0 is similar to type 2, we can slightly modify the proof of Theorem 16 to obtain a proof of this theorem. In fact, types 0 and 2 are the same when the number of digits k +1 is even. In this proof, unless stated otherwise, b-adic antipalindromes are of type 0. Let n ≥ b and let n = (n_{k}n_{k−1} ⋯ n_{0})_{b} be a b-adic antipalindrome with n_{k} ≠ 0. Let m = f_{0}(n).

By the definition of type 0, we obtain that k is odd. So the three cases of even integer k in Theorem 16 do not occur in this proof. In addition, it is straightforward to check that if b ≤ n ≤ b^{3}, then n ≤ (b − 1)b and

\frac{m − n}{n} ≤ max \{\frac{b − 1}{b + (b − 2)}, \frac{b^{3} + (b − 2)}{(b − 1)b}\} = \frac{b^{2} + b + 2}{b}

= (b − 1) (1 + \frac{2(b + 1)}{(b − 1)b}) < c_{n}(b − 1).

So we assume that n ≥ b^{3} + 1. So k ≥ 3. Furthermore, if n_{\frac{k+1}{2}} ≠ b − 1, then we can use exactly the same calculation as in Case 1 of Theorem 16 to obtain

m − n ≤ (\sqrt{b} − \sqrt{b^{−1}}) \sqrt{n} < (b − 1)c_{n}n.  (29)

So it remains to consider the results corresponding to Cases 5 and 6 in Theorem 16.

Case 1: k is odd, n_{\frac{k+1}{2}} = b − 1, and n_{i} ≠ b − 1 for some i > \frac{k+1}{2}. This is the same as in Case 6 in Theorem 16 and the same calculation still work. Therefore

m − n ≤ 2\sqrt{b}\sqrt{n} < (b − 1)c_{n}n.  (30)

Case 2: k is odd and n_{i} = b − 1 for all i ≥ \frac{k+1}{2}. This is similar to Case 5 in Theorem 16. We have n = b^{k+1} − b^{\frac{k+1}{2}} and f_{2}(n) = b^{k+1} + b^{\frac{k+1}{2}} − 2. By Lemma 15, we obtain f_{0}(n) ≥ f_{2}(n) ≥ b^{k+1}. Since k + 1 is even, the integers in the interval [b^{k+1}, b^{k+2}) are not b-adic antipalindromes of type 0. So f_{0}(n) ≥ b^{k+2}. Since k + 2 is odd, types 0 and 2 are the same in the interval [b^{k+2}, b^{k+3}). Therefore the smallest b-adic antipalindrome of types 0 and 2 that is larger than b^{k+2} is the same too. Thus

m = f_{0}(n) = f_{2} (b^{k+2}) = b^{k+2} + b^{\frac{k+3}{2}} − 2.

Since n < b^{k+1} − 1, we have

\frac{m − n}{n} = \frac{b^{k+2} − b^{k+1}}{b^{k+1} − b^{\frac{k+1}{2}}} + \frac{b^{\frac{k+3}{2}} + b^{\frac{k+1}{2}}}{b^{k+1} − b^{\frac{k+1}{2}}} − \frac{2}{b^{k+1} − b^{\frac{k+1}{2}}}

= (b − 1) (1 + \frac{1}{b^{\frac{k+1}{2}} − 1} + \frac{b + 1}{(b − 1) (b^{\frac{k+1}{2}} − 1)}) − \frac{2}{b^{k+1} − b^{\frac{k+1}{2}}}  (31)

< (b − 1) (1 + \frac{2b}{(b − 1) (b^{\frac{k+1}{2}} − 1)})

< (b − 1) (1 + \frac{2b}{(b − 1) (\sqrt{n + 1} − 1)}) = (b − 1)c_{n}.

This proves x_{n+1} − x_{n} < (b − 1)c_{n}x_{n} for all n ≥ 1. Then it also follows that the limit supremum of (x_{n+1} − x_{n})/x_{n} is less than or equal to b − 1. Furthermore, we obtain from (31) that (m − n)/n converges to b − 1 as k → ∞. This proves the remaining parts of this theorem.

Corollary 19. Let b be an integer not less than 2. If a positive real number ε is given, then the interval (n, (b + ε)n) contains a b-adic antipalindrome of type 0 (no middle type) for all large n, and there are infinitely many m ∈ ℕ such that the interval (m, (b − ε)m] does not contain a b-adic antipalindrome of type 0.

Proof. This follows immediately from the limit supremum in Theorem 18.

If b is even, then the equality 2n_{\frac{k}{2}} = b − 1 is not possible, and so types 0 and 1 are equivalent. If b is odd, then type 1 is a bit different from types 0 and 2 as shown in the next theorem.

Theorem 20. Let b be an integer not less than 2 and (x_{n}) the strictly increasing sequence of b-adic antipalindromes of type 1 (one middle type). Then the following statements hold.

(i) If b is even, then x_{n+1} − x_{n} < (b − 1)c_{n}x_{n} for all n ∈ ℕ, and

lim sup_{n→∞} \frac{x_{n+1} − x_{n}}{x_{n}} = b − 1,

where c_{n} is defined as (28).

(ii) If b is odd, then x_{n+1} − x_{n} ≤ (b + 1)\sqrt{x_{n}} for all n ∈ ℕ, and

lim sup_{n→∞} \frac{x_{n+1} − x_{n}}{\sqrt{x_{n}}} = b + 1.

Proof. The statement (i) follows immediately from Theorem 18. So we only need to prove (ii). In this proof, unless stated otherwise, all b-adic antipalindromes are of type 1. Assume that b is odd, n is a b-adic antipalindrome represented as n = (n_{k}n_{k−1} ⋯ n_{0})_{b} with n_{k} ≠ 0, and m = f_{1}(n). By listing all b-adic antipalindromes in [1, b^{3}), it is straightforward to check that if n ≤ b^{3}, then m − n ≤ (b + 1)\sqrt{n}. So assume that n ≥ b^{3}. Therefore k ≥ 3. If k is even, then n_{\frac{k}{2}} = \frac{b−1}{2} ≠ b − 1. So Cases 3 and 4 in the proof of Theorem 16 do not occur here, but we cannot simply follow Case 2 in Theorem 16 because when k is even, the middle digits of m and n are fixed to be \frac{b−1}{2}. We still need to split the calculation into 5 cases as follows.

Case 1: k is even and n_{i} ≠ b − 1 for some i > \frac{k}{2}. Then n_{i} ≠ 0 for some i < \frac{k}{2}. Let j be the largest integer less than \frac{k}{2} such that n_{j} ≠ 0. Then n_{k−j} ≠ b−1. Let y = b^{\frac{k}{2} +1} +b^{\frac{k}{2}} −b^{j+1} −b^{j}. Then n + y is a b-adic antipalindrome. Therefore

m − n ≤ y < b^{\frac{k}{2} +1} + b^{\frac{k}{2}} = (b + 1)b^{\frac{k}{2}} < (b + 1)\sqrt{n}.  (32)

Case 2: k is even and n_{i} = b − 1 for all i > \frac{k}{2}. Then n_{i} = 0 for all i < \frac{k}{2}. Then n = b^{k+1} − b^{\frac{k}{2} +1} + (\frac{b−1}{2}) b^{\frac{k}{2}} . Let

y = b^{\frac{k}{2} +1} + (\frac{b + 1}{2}) b^{\frac{k}{2}} − 2

= b^{\frac{k}{2} +1} + (\frac{b − 1}{2}) b^{\frac{k}{2}} + (b − 1) ∑_{0<i< \frac{k}{2}} b^{i} + (b − 2).

Then n + y is a b-adic antipalindrome. Recall that k ≥ 3 and k is even. So k ≥ 4. Moreover, b ≥ 3 since b ≥ 2 and b is odd. Therefore

\frac{m − n}{\sqrt{n}} ≤ \frac{y}{\sqrt{n}} < \frac{2b^{\frac{k}{2} +1}}{\sqrt{b^{k+1} − b^{\frac{k}{2} +1}}} = \frac{2\sqrt{b}}{\sqrt{1 − b^{− \frac{k}{2}}}} ≤ \frac{2\sqrt{b}}{\sqrt{1 − b^{−2}}} < b + 1.

So we have m − n < (b + 1)\sqrt{n}.

Case 3: k is odd and n_{\frac{k+1}{2}} ≠ b − 1. Then we follow Case 1 of Theorem 16 to obtain

m − n ≤ (\sqrt{b} − \sqrt{b^{−1}})\sqrt{n} ≤ (b + 1)\sqrt{n}.

Case 4: k is odd, n_{\frac{k+1}{2}} = b − 1, and n_{i} ≠ b − 1 for some i > \frac{k+1}{2}. This is the same as Case 6 of Theorem 16 and the same calculation still works. Therefore

m − n < 2\sqrt{b}\sqrt{n} ≤ (b + 1)\sqrt{n}.

Case 5: k is odd and n_{i} = b − 1 for all i ≥ \frac{k+1}{2}. This is similar to Case 5 in Theorem 16 and Case 2 in Theorem 18. Then n = b^{k+1} − b^{\frac{k+1}{2}} and f_{2}(n) = b^{k+1} + b^{\frac{k+1}{2}} − 2. By Lemma 15, we have f_{1}(n) ≥ f_{2}(n) ≥ b^{k+1}. Since k + 1 is even, the b-adic antipalindromes of type 1 in the interval [b^{k+1}, b^{k+2}) have their middle digit (the digit corresponding to b^{\frac{k+1}{2}} ) equal to \frac{b−1}{2}. Since f_{2}(n) is a b-adic antipalindrome of type 2 having middle digit equal to 0 and f_{1}(n) > f_{2}(n), we see that m = f_{1}(n) = f_{2}(n) + (\frac{b−1}{2}) b^{\frac{k+1}{2}} . Therefore

\frac{m − n}{\sqrt{n}} = \frac{(\frac{b+3}{2}) b^{\frac{k+1}{2}} − 2}{\sqrt{b^{k+1} − b^{\frac{k+1}{2}}}} < \frac{b + 3}{2\sqrt{1 − b^{− \frac{k+1}{2}}}}  (33)

≤ \frac{b + 3}{2\sqrt{1 − b^{−2}}} < b + 1.

From Cases 1–5, we obtain x_{n+1} − x_{n} ≤ (b + 1)\sqrt{x_{n}} for all n ≥ 1. For the limit supremum, we construct the integers n as in Case 1 where k ≥ 10, k is even, j = ⌊k/3⌋, and

n = b^{k} + b^{k−j} − b^{\frac{k}{2} +1} + (\frac{b − 1}{2}) b^{\frac{k}{2}} + b^{j+1} − 2.

By Lemma 15, we obtain m = n + y where y = b^{\frac{k}{2} +1} + b^{\frac{k}{2}} − b^{j+1} − b^{j}. It is easy to verify that y/\sqrt{n} converges to b + 1 as k → ∞. Therefore (m − n)/\sqrt{n} converges to b + 1 as n → ∞. This proves the remaining part of this theorem.

Corollary 21. If b ≥ 2 and b is even, then type 0 (no middle type) in Corollary 19 can be replaced by type 1 (one middle type), and the same result holds. If b ≥ 3, b is odd, and ε > 0, then the interval (n, n + (b + 1)\sqrt{n}] contains a b-adic antipalindrome of type 1 for all n ≥ b, and there are infinitely many m ∈ ℕ such that the interval (m, m + (b + 1 − ε)\sqrt{m}] does not contain a b-adic antipalindrome of type 1.

Proof. This follows immediately from the limit supremum in Theorem 20.

2.4 Antipalindromes of type 3 in short intervals

Recall that the antipalindromes of type 3 (asymmetric type) are those with the property n_{k−i} ≠ n_{i} for 0 ≤ i ≤ ⌊(k − 1)/2⌋. We begin with a lemma on f_{3}(n) as follows.

Lemma 22. Let b be an integer not less than 3. Then the following statements hold.

(i) If k ≥ 1 and n = b^{k+1} − 1 − ^{\frac{b^{⌈^{\frac{k}{2}}⌉}−1}{b−1}}, then

f_{3}(n) = b^{k+1} + \frac{b^{⌈^{\frac{k+1}{2}}⌉} − 1}{b − 1} − 1.  (34)

(ii) If k is odd, k ≥ 11, j = ⌊k/3⌋, and n = b^{k} + b^{k−j} − \frac{b^{\frac{k+1}{2}} −b^{j+1}}{b−1} − 1, then

f_{3}(n) = b^{k} + b^{k−j} + \frac{b^{\frac{k+1}{2}} − b^{j+1}}{b − 1} + \frac{b^{j} − b}{b − 1}.  (35)

Proof. Let n be defined as in (i) and let m be the number on the right-hand side of (34). Then

n = (b − 1) ∑_{⌈\frac{k}{2}⌉≤i≤k} b^{i} + (b − 2) ∑_{0≤i<⌈\frac{k}{2}⌉} b^{i} and

m = b^{k+1} + ∑_{0<i<⌈\frac{k+1}{2}⌉} b^{i}.

Let y = (y_{k}y_{k−1} ⋯ y_{0})_{b} and n < y ≤ b^{k+1} − 1. By comparing the digits of n, y, and b^{k+1} − 1, we see that y_{i} = b − 1 for ⌈\frac{k}{2}⌉ ≤ i ≤ k and y_{j} = b − 1 for some j < ⌈\frac{k}{2}⌉. This implies that y_{j} = y_{k−j}, and so y is not a b-adic antipalindrome of type 3. This shows that there is no b-adic antipalindrome of type 3 in the interval (n, b^{k+1}). In addition, the integer b^{k+1} is not a b-adic antipalindrome of type 3. Therefore f_{3}(n) > b^{k+1}. It is easy to see that m is a b-adic antipalindrome of type 3 larger than n. Thus b^{k+1} < f_{3}(n) ≤ m. Next, let z = (z_{k+1}z_{k} ⋯ z_{0})_{b} and b^{k+1} < z < m. Then z_{k+1} = 1 and z_{i} = 0 for ⌈\frac{k+1}{2}⌉ ≤ i ≤ k. If z_{i} ≠ 0 for every i ∈ (0, ⌈\frac{k+1}{2}⌉), then z_{i} = 1 for all i ∈ (0, ⌈\frac{k+1}{2}⌉), which implies z ≥ m, a contradiction. Therefore z_{j} = 0 for some j ∈ (0, ⌈\frac{k+1}{2}⌉). So z_{j} = z_{k+1−j} and z is not a b-adic antipalindrome of type 3. This implies that f_{3}(n) ≥ m. Hence f_{3}(n) = m, as required.

Next, we prove (ii). So let n be defined as in (ii) and let m be the number on the right-hand side of (35). Then

n = b^{k} + (b − 1) ∑_{\frac{k+1}{2} ≤i<k−j} b^{i} + (b − 2) ∑_{j<i< \frac{k+1}{2}} b^{i} + (b − 1) ∑_{0≤i≤j} b^{i},

n + ∑_{j<i< \frac{k+1}{2}} b^{i} = b^{k} + b^{k−j} − 1, and

m = b^{k} + b^{k−j} + ∑_{j<i< \frac{k+1}{2}} b^{i} + ∑_{0<i<j} b^{i}.

Let y = (y_{k}y_{k−1} ⋯ y_{0})_{b}. Suppose that n < y ≤ b^{k} + b^{k−j} − 1. Then y_{i} = n_{i} for \frac{k+1}{2} ≤ i ≤ k. If y_{i} ≠ b − 1 for every i ∈ (j, \frac{k+1}{2}), then y_{i} = b − 2 for all i ∈ (j, \frac{k+1}{2}), which implies y = n, a contradiction. Therefore y_{i} = b − 1 for some i ∈ (j, \frac{k+1}{2}). Then y_{i} = y_{k−i} and so y is not a b-adic antipalindrome of type 3. This shows that there is no b-adic antipalindrome of type 3 in the interval (n, b^{k} + b^{k−j} − 1]. It is easy to check that m is a b-adic antipalindrome of type 3 larger than n. Therefore

b^{k} + b^{k−j} ≤ f_{3}(n) ≤ m.

Suppose b^{k} + b^{k−j} ≤ y < m. We will show that y is not a b-adic antipalindrome of type 3. We have y_{i} = m_{i} for all i ∈ [\frac{k+1}{2}, k]. If y_{i} = 0 for some i ∈ (j, \frac{k+1}{2}), then y_{i} = y_{k−i} and we are done. So we can assume that y_{i} = 1 for all i ∈ (j, \frac{k+1}{2}). Then y_{j} = 0. If y_{i} ≠ 0 for every i ∈ (0, j), then y_{i} = 1 for all i ∈ (0, j), which implies y ≥ m, a contradiction. So y_{i} = 0 for some i ∈ (0, j). Thus y_{i} = y_{k−i} and y is not a b-adic antipalindrome of type 3. This shows that there is no b-adic antipalindrome of type 3 in the interval [b^{k} + b^{k−j}, m). Hence f_{3}(n) = m, and the proof is complete.

Remark 23. If b = 2, then the b-adic antipalindromes of types 2 and 3 are the same. The constants 2\sqrt{b} in Theorem 16 and \frac{2\sqrt{b}}{b−1} in Theorem 24 are also the same when b = 2. So we do not need to give a proof of Theorem 24 when b = 2.

Theorem 24. Let b be an integer not less than 2, c = \frac{2\sqrt{b}}{b−1}, and (x_{n}) the strictly increasing sequence of b-adic antipalindromes of type 3 (asymmetric type). Then x_{n+1} − x_{n} ≤ c\sqrt{x_{n}} for all n ≥ b and

lim sup_{n→∞} \frac{x_{n+1} − x_{n}}{\sqrt{x_{n}}} = c.

Proof. By Remark 23, we can assume that b ≥ 3. Unless stated otherwise, all b-adic antipalindromes in this proof are of type 3. Let n be a b-adic antipalindrome represented as n = (n_{k}n_{k−1} ⋯ n_{0})_{b}, where n_{k} ≠ 0. Let m be the smallest b-adic antipalindrome larger than n. By listing all b-adic antipalindromes less than b^{3}, it is straightforward to check that if b ≤ n < b^{3}, then m − n ≤ c\sqrt{n}. So we can assume that n ≥ b^{3}, and so k ≥ 3. Before proceeding further, we first give the following observation that will be used throughout the proof:

(A1) If there exists an integer i ≤ ⌊\frac{k−1}{2}⌋ such that n_{i} ≠ b − 1 and n_{i} + 1 ≠ n_{k−i}, then m − n < c\sqrt{n}.

(A2) If there is an integer i ≤ ⌊\frac{k−1}{2}⌋ such that n_{i} ≤ b − 3, then m − n < c\sqrt{n}.

(A3) If k is odd and n_{\frac{k−1}{2}} = b − 1, then m − n < c\sqrt{n}.

To prove (A1), we only need to observe that if the condition in (A1) is satisfied, then n + b^{i} is a b-adic antipalindrome, and therefore

\frac{m − n}{\sqrt{n}} ≤ \frac{b^{i}}{\sqrt{n}} ≤ \frac{b^{⌊^{\frac{k−1}{2}}⌋}}{b^{\frac{k}{2}}} ≤ \frac{1}{\sqrt{b}} < c.

Next, if the condition in (A2) is satisfied, then n + b^{i} or n + 2b^{i} is a b-adic antipalindrome, and so

\frac{m − n}{\sqrt{n}} ≤ \frac{2b^{i}}{\sqrt{n}} ≤ \frac{2b^{⌊^{\frac{k−1}{2}}⌋}}{b^{\frac{k}{2}}} ≤ \frac{2}{\sqrt{b}} < c.

Finally, suppose that the condition in (A3) is satisfied. Then n_{\frac{k+1}{2}} ≠ b − 1. So n + b^{\frac{k−1}{2}} is a

b-adic antipalindrome. Therefore m − n ≤ b^{\frac{k−1}{2}} ≤ \sqrt{n}/\sqrt{b} < c\sqrt{n}.

We now proceed to give a proof of this theorem.

Case 1: k is odd and n_{i} = b − 2 for all i < \frac{k−1}{2}. By (A2) and (A3), we can assume that n_{\frac{k−1}{2}} = b − 2. Then by (A1), we can further assume that n_{i} + 1 = n_{k−i} for all i ≤ \frac{k−1}{2}.

Therefore n_{k−i} = b − 1 for all i ≤ \frac{k−1}{2}. By Lemma 22, we obtain m = b^{k+1} + \frac{b^{\frac{k+1}{2}} −1}{b−1} − 1. In addition, we have n ≥ b^{k+1} − b^{\frac{k+1}{2}} . Therefore

\frac{m − n}{\sqrt{n}} = \frac{2}{b − 1} (\frac{b^{\frac{k+1}{2}} − 1}{\sqrt{n}}) < \frac{2}{b − 1} (\frac{b^{\frac{k+1}{2}}}{\sqrt{b^{k+1} − b^{\frac{k+1}{2}}}} )

= \frac{2}{b − 1} (\frac{1}{\sqrt{1 − b^{− \frac{k+1}{2}}}} ) ≤ \frac{2}{b − 1} (\frac{1}{\sqrt{1 − b^{−1}}} ) < c.

Case 2: k is odd and n_{i} ≠ b − 2 for some i < \frac{k−1}{2}. Similar to Case 1, by applying (A2) and (A3), we can assume that n_{\frac{k−1}{2}} = b − 2 and n_{i} ∈ \{b − 2, b − 1\} for all i < \frac{k−1}{2}. By (A1), we can also assume that

if i ≤ \frac{k − 1}{2} and n_{i} ≠ b − 1, then n_{i} + 1 = n_{k−i}.  (36)

So, in particular, n_{\frac{k+1}{2}} = b − 1, and for 0 ≤ i < \frac{k−1}{2}, we have n_{i} = b − 2 if and only if n_{k−i} = b − 1. If n_{i} = b − 1 for all i > \frac{k+1}{2}, then n_{i} = b − 2 for all i ≤ \frac{k−1}{2}, which is not the case we are considering. So n_{i} ≠ b − 1 for some i > \frac{k+1}{2}. For convenience, let i_{0} be the smallest integer larger than \frac{k+1}{2} such that n_{i_{0}} ≠ b − 1 and write i_{0} = k − j where j < \frac{k−1}{2}. Then n_{i} = b − 2 and n_{k−i} = b − 1 for all i ∈ (j, \frac{k−1}{2}]. Let y_{0} = b − n_{0} and y_{i} = b − 1 − n_{i} for 0 < i ≤ \frac{k−1}{2}. In addition, let z_{0} = z_{j} = 0, z_{i} = 1 for j < i ≤ \frac{k−1}{2}, and z_{i} = max\{0, 1 − n_{k−i}\} for 0 < i < j. Then for i ∈ (0, j), we have z_{i} ∈ {0, 1}, z_{i} = 0 if and only if n_{k−i} ≠ 0, and z_{i} = 1 if and only if n_{k−i} = 0. Let

y = ∑_{0≤i≤ \frac{k−1}{2}} y_{i}b^{i} and z = ∑_{0≤i≤ \frac{k−1}{2}} z_{i}b^{i}.

Then

n + y = ∑_{k−j<i≤k} n_{i}b^{i} + (n_{k−j} + 1)b^{k−j},
n + y + z = ∑_{k−j<i≤k} n_{i}b^{i} + (n_{k−j} + 1)b^{k−j} + ∑_{j<i≤ \frac{k−1}{2}} b^{i} + ∑_{0<i<j} z_{i}b^{i}.

Then n + y + z is a b-adic antipalindrome, and so m − n ≤ y + z. Since n_{i} ∈ {b − 1, b − 2} for all i ∈ [0, \frac{k−1}{2}], we see that y_{0} ≤ 2 and y_{i} ≤ 1 for all i ∈ (0, \frac{k−1}{2}]. In addition, we have z_{0} = 0 and z_{i} ≤ 1 for all i ∈ (0, \frac{k−1}{2}]. Therefore y_{i} + z_{i} ≤ 2 for all i ∈ [0, \frac{k−1}{2}]. Hence

m − n ≤ y + z ≤ 2 ∑_{0≤i≤ \frac{k−1}{2}} b^{i} = \frac{2}{b − 1} (b^{\frac{k+1}{2}} − 1) < \frac{2b^{\frac{k+1}{2}}}{b − 1} ≤ c\sqrt{n}.

Case 3: k is even and n_{i} = b − 2 for all i < \frac{k}{2}. By (A1), we can assume that n_{k−i} = b − 1 for all i < \frac{k}{2}. If n_{\frac{k}{2}} ≠ b − 1, then n + 1 + ∑_{0≤i< \frac{k}{2}} b^{i} is a b-adic antipalindrome, and therefore

\frac{m − n}{\sqrt{n}} ≤ \frac{1 + ∑_{0≤i< \frac{k}{2}} b^{i}}{\sqrt{n}} ≤ \frac{1 + \frac{b^{\frac{k}{2}} −1}{b−1}}{b^{\frac{k}{2}}} < \frac{1}{b^{\frac{k}{2}}} + \frac{1}{b − 1} < c.

So we can assume that n_{\frac{k}{2}} = b − 1. Then n = b^{k+1} − 1 − \frac{b^{\frac{k}{2}} −1}{b−1} which is in the form suitable for the application of Lemma 22. Therefore

m = b^{k+1} + \frac{b^{\frac{k+2}{2}} − 1}{b − 1} − 1,

and so

\frac{m − n}{\sqrt{n}} = \frac{b^{\frac{k+2}{2}} + b^{\frac{k}{2}} − 2}{(b − 1)\sqrt{n}} < \frac{b^{\frac{k+2}{2}} + b^{\frac{k}{2}}}{(b − 1)\sqrt{b^{k+1} − b^{\frac{k}{2}}}}

= \frac{\sqrt{b} + \sqrt{b^{−1}}}{(b − 1)\sqrt{1 − b^{− \frac{k+2}{2}}}} ≤ \frac{\sqrt{b} + \sqrt{b^{−1}}}{(b − 1)\sqrt{1 − b^{−3}}} < c.

Case 4: k is even and n_{i} ≠ b − 2 for some i < \frac{k}{2}. By (A1) and (A2), for all i < \frac{k}{2}, we can assume that n_{i} ∈ {b − 2, b − 1} and that n_{i} = b − 2 if and only if n_{k−i} = b − 1.

Case 4.1: n_{\frac{k}{2}} ≠ b − 1. We will define y and z similar to those in Case 2. Let y_{0} = b − n_{0} and y_{i} = b − 1 − n_{i} for 0 < i < \frac{k}{2}. In addition, let z_{0} = 0 and z_{i} = max\{0, 1 − n_{k−i}\} for 0 < i < \frac{k}{2}. Then z_{i} = 0 if and only if n_{k−i} ≠ 0, and z_{i} = 1 if and only if n_{k−i} = 0. Let

y = ∑_{0≤i< \frac{k}{2}} y_{i}b^{i} and z = ∑_{0≤i< \frac{k}{2}} z_{i}b^{i}.

Similar to Case 2, we obtain that n + y + z is a b-adic antipalindrome, and y_{i} + z_{i} ≤ 2 for all i < \frac{k}{2}. Therefore

\frac{m − n}{\sqrt{n}} ≤ \frac{y + z}{\sqrt{n}} ≤ \frac{2 (\frac{b^{\frac{k}{2}} −1}{b−1})}{b^{\frac{k}{2}}} < \frac{2}{b − 1} < c.

Case 4.2: n_{\frac{k}{2}} = b − 1. Similar to Case 2, there exists i > \frac{k}{2} such that n_{i} ≠ b − 1, and we write k − j for the smallest integer larger than \frac{k}{2} such that n_{k−j} ≠ b − 1 where j < \frac{k}{2}. Then n_{i} = b−2 and n_{k−i} = b−1 for all i ∈ (j, \frac{k}{2}). Let y_{0} = b−n_{0} and y_{i} = b−1−n_{i} for 0 < i < \frac{k}{2}. In addition, let z_{0} = z_{j} = 0, z_{i} = 1 for j < i < \frac{k}{2}, and z_{i} = max\{0, 1 − n_{k−i}\} for 0 < i < j. Then similar to Case 2, we obtain n + y + z is a b-adic antipalindrome and y_{i} + z_{i} ≤ 2 for all i < \frac{k}{2}. Therefore

\frac{m − n}{\sqrt{n}} ≤ \frac{y + z}{\sqrt{n}} ≤ \frac{2 (\frac{b^{\frac{k}{2}} −1}{b−1})}{b^{\frac{k}{2}}} < \frac{2}{b − 1} < c.

From the calculation in all cases, we conclude that x_{n+1} − x_{n} ≤ c\sqrt{n} for all n ≥ b. For the limit supremum, we let n be defined as in (ii) of Lemma 22, where k ≥ 11, k is odd, and j = ⌊k/3⌋. Then

m = f_{3}(n) = b^{k} + b^{k−j} + \frac{b^{\frac{k+1}{2}} − b^{j+1}}{b − 1} + \frac{b^{j} − b}{b − 1}.

Therefore

\frac{m − n}{\sqrt{n}} = \frac{1}{\sqrt{n}} (\frac{2}{b − 1} (b^{\frac{k+1}{2}} − b^{j+1}) + \frac{b^{j} − b}{b − 1} + 1)

= \frac{\frac{2}{b−1} (\sqrt{b} − b^{j+1− \frac{k}{2}} ) + \frac{1}{b−1} (b^{j− \frac{k}{2}} − b^{1− \frac{k}{2}} ) + b^{− \frac{k}{2}}}{\sqrt{1 + b^{−j} − \frac{b^{\frac{1−k}{2}}}{b−1} + \frac{b^{j+1−k}}{b−1} − b^{−k}}} ,

which converges to c as k → ∞. This completes the proof.

3 Comments and questions

Let P_{b} be the set of all b-adic palindromes. In this paper, we determine all integers d such that R(b; d) is infinite, where R(b; d) is defined in (5). Instead of the infinitude of R(b; d), it is also interesting to consider an integer d satisfying R(b; d) ≠ ∅. Recall that for each X ⊆ ℝ, we define the difference set D(X) as D(X) = {x − y | x, y ∈ X}. Then for each d ∈ ℕ, the set R(b; d) is not empty if and only if d ∈ D(P_{b}). So we propose the following questions.

Question 25. For each k ∈ ℕ, does D(P_{b}) contain an arithmetic progression of length k? Does D(P_{b}) have positive upper asymptotic density? That is, does

lim sup_{N→∞} \frac{#(D(P_{b}) ∩ [−N, N])}{2N + 1} > 0 hold?

Does D(P_{b}) contain infinite arithmetic progressions?

Question 26. Let r(d) be the number of x, y ∈ P_{b} satisfying d = x−y. Is there an asymptotic formula of ∑_{|d|≤x, r(d)<∞} r(d)? For every d ∈ ℤ with r(d) < ∞, can we find some upper or lower bounds for r(d)?

Let S be the set of all perfect squares. Let r be a positive integer, and let S = C_{1}∪⋯∪C_{r}. It is unknown whether or not there exists an arithmetic progression of length 3 in C_{i} for some i = 1, 2, …, r. We are interested in the gaps and other analogous results between squares and palindromes. Thus we would like to consider the following question.

Question 27. For each positive integer r, if P_{b} = C_{1} ∪ ⋯ ∪ C_{r}, then does some C_{i} contain an arithmetic progression of length 3? More generally, for every A ⊆ P_{b} with positive upper relative density, that is

lim sup_{N→∞} \frac{#(A ∩ [1, N])}{#(P_{b} ∩ [1, N])} > 0,

must A contain an arithmetic progression of length 3?

4 Acknowledgments

We would like to thank Yuuya Yoshida for asking us a question concerning palindromes in short intervals and giving a comment for improving Theorem 18. The referee carefully read our manuscript and gave us many comments and suggestions that greatly improved the presentation 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. 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.

Kota Saito is supported by JSPS KAKENHI Grant Number JP22J00025 and JP22KJ0375.

References

[1] G. E. Andrews, M. Just, and G. Simay, Anti-palindromic compositions, Fibonacci Quart. 60(2) (2022), 164–176.

[2] J. H. Bai, J. Meleshko, S. Riasat, and J. Shallit, Quotient of palindromic and antipalindromic numbers, Integers 22 (2022), Article #A96.

[3] P. B. Borwein, On the irrationality of certain series, Math. Proc. Camb. Phil. Soc. 112 (1992), 141–146.

[4] V. Brun, La série 1/5 + 1/7 + 1/11 + 1/13 + 1/17 + 1/19 + 1/29 + 1/31 + 1/41 + 1/43+ 1/59+1/61+⋯, où les dénominateurs sont ‘nombres premiers jumeaux’est convergente ou finie, Bull. Sci. Math. (2) 43 (1919), 124–128.

[5] P. Bundschuh and K. Väänänen, Linear independence of q-analogues of certain classical constants, Results Math. 47 (2005), 33–44.

[6] L. Dvořáková, S. Kruml, and D. Ryzak, Antipalindromic numbers, Acta Polytechnica 61(3) (2021), 428–434.

[7] J. Huang, Partially palindromic compositions, J. Integer Sequences 26 (2023), Article 23.4.1.

[8] P. Napp Phunphayap and P. Pongsriiam, A complete comparison for the number of palindromes in different bases, AIMS Math. 8(4) (2023), 9924–9932.

[9] P. Phunphayap and P. Pongsriiam, Extremal orders and races between palindromes in different bases, AIMS Math. 7(2) (2022), 2237–2254.

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

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

[12] 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.

[13] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, online resource, 2023.

    Available at https://oeis.org.

[14] Y. Tachiya, Irrationality of certain Lambert series, Tokyo J. Math. 27(1) (2004), 75–85.

2020 Mathematics Subject Classification: Primary 11A63; Secondary 11B05, 11J72. Keywords: palindrome, antipalindrome, gap, digital problem, irrationality.

(Concerned with sequences \underline{A002113}, \underline{A002385}, and \underline{A035928}.)

Received July 19 2023; revised version received December 6 2023. Published in Journal of Integer Sequences, December 11 2023.

Return to Journal of Integer Sequences home page.