The palindrome counting function

Question

Let $b \geq 2$ be a positive integer and consider the function $f_b : \mathbb{N}^+ \to \mathbb{N}^+$ given by $$f_b (n) = |\{ k \in \mathbb{N}^+ : k \leq n \mbox{ and } k \mbox{ is palindromic in base } b\}|.$$ A simple counting argument shows that: $$f_b (b^k) = \begin{cases} (1+b) b^{\frac{k-1}{2}} - 2& \mbox{if } k \mbox{ is odd } \\ 2 \cdot b^{\frac{k}{2}} - 2 & \mbox{if } k \mbox{ is even} \end{cases}$$ Using the monotonicity of $f_b$ and the previous fact, together with the inequality $b^{\lfloor \log_b n \rfloor} \leq n \leq b^{1 + \lfloor \log_b n \rfloor}$ we get the following $$\frac{2\sqrt{b}}{b} \sqrt{n} - 2\leq 2 b^{\frac{\lfloor \log_b n \rfloor}{2}} - 2 \leq f_b(n) \leq (1+b)b^{\frac{\lfloor \log_b n \rfloor}{2}} \leq (1+b) \sqrt{n} - 2$$ From this it follows that $$ \frac{2\sqrt{b}}{b} - 2\frac{\sqrt{n}}{n} \leq \frac{f_b(n)}{\sqrt{n}} \leq (1+b) - 2\frac{\sqrt{n}}{n}$$ Consider the function $g_b: \mathbb{N}^+ \to \mathbb{N}^+$ given by $$g_b (n) = \frac{f_b(n)}{\sqrt{n}} \hspace{3mm} \forall n \in \mathbb{N}^+$$ The previous facts imply that $g_b$ is a bounded positive function, and that $$\frac{2\sqrt{b}}{b} \leq \liminf_{n \to \infty} g_b (n) \leq \limsup_{n \to \infty} g_b(n) \leq 1 + b$$ Computational evidence suggests that $$\liminf_{n \to \infty} g_b(n) = 2 \hspace{3mm} \mbox{ and } \hspace{3mm} \limsup_{n \to \infty} g_b(n) = \frac{(1+b)\sqrt{b}}{b}$$ How can i prove it? I think i need tighter bounds, and therefore a better and non trivial way to count palindromes.

Answer 1

The proof is by me, not from any source, sorry.

Let $n$ be $k$-digit number in base $b$. Let $n=a_{k-1}a_{k-2}\dots a_0$. We split the interval $[0,n]$ to $[0,b^{k-1}), [b^{k-1},a_{k-1}a_{k-2}\dots a_{\lfloor k/2\rfloor}0\dots 0),[a_{k-1}a_{k-2}\dots a_{\lfloor k/2\rfloor}0\dots 0,n]$.

We count the number of palindrome numbers in each interval.

(1) $k$ is odd

The first interval $[0,a_{k-1}000\dots 0)$ counts all the palindromes with $\le k-1$ digits and all the palindromes with $k$ digits and first digit is $1,\dots,a_{k-1}-1$. The number of the palindromes with $\le k-1$ digits is $2b^{(k-1)/2}-2$.

The last interval has first $\frac{k+1}2$ numbers fixed, so it has at most one palindrome numbers. Let $r$ be the number of palindromes in this interval, and $r\in\{0,1\}$

The second interval has $a_{k-1}a_{k-2}\dots a_{(k-1)/2}-b^{(k-1)/2}$ palindromes, since we can map any palindrome, by taking its first $(k+1)/2$ digits, to a number from $b^{(k-1)/2}$ to $a_{k-1}a_{k-2}\dots a_{(k-1)/2}-1$. Also, for each number in $b^{(k-1)/2}$ to $a_{k-1}a_{k-2}\dots a_{(k-1)/2}-1$, we can write its first $(k-1)/2$ digits reversely to its end, and it is in the second interval.

So the number of palindrome is

$$2b^{(k-1)/2}-2+a_{k-1}a_{k-2}\dots a_{(k-1)/2}-b^{(k-1)/2}+r\\=b^{(k-1)/2}+a_{k-1}a_{k-2}\dots a_{(k-1)/2}+O(1)=b^{(k-1)/2}+\frac{n}{b^{(k-1)/2}}+O(1)$$

So

$$g_b(n)=\frac{b^{(k-1)/2}+\frac{n}{b^{(k-1)/2}}}{\sqrt{n}}+O(\frac{1}{\sqrt n})=\frac{b^{(k-1)/2}}{\sqrt{n}}+\frac{\sqrt{n}}{b^{(k-1)/2}}+O(\frac{1}{\sqrt n})$$

Notice that $n$ is from $[b^{k-1},b^k]$, so $g_b(n)$ takes value from $[2+O(\frac{1}{\sqrt n}),\frac{1+b}{\sqrt{b}}+O(\frac{1}{\sqrt n})]$

(2) $k$ is even

Everything is similar. The first interval $[0,a_{k-1}000\dots 0)$ counts all the palindromes with $\le k-1$ digits and all the palindromes with $k$ digits and first digit is $1,\dots,a_{k-1}-1$. The number of the palindromes with $\le k-1$ digits is $(b+1)b^{(k-2)/2}-2$.

The last interval has first $\frac{k}2$ numbers fixed, so it has at most one palindrome numbers. Let $r$ be the number of palindromes in this interval, and $r\in\{0,1\}$

The second interval has $a_{k-1}a_{k-2}\dots a_{k/2}-b^{(k-2)/2}$ palindromes, since we can map any palindrome, by taking its first $k/2$ digits, to a number from $b^{(k-2)/2}$ to $a_{k-1}a_{k-2}\dots a_{(k-1)/2}-1$. Also, for each number from $b^{(k-2)/2}$ to $a_{k-1}a_{k-2}\dots a_{(k-1)/2}-1$, we can write all its digits reversely to its end, and it is in the second interval.

So the number of palindrome is

$$(b+1)b^{(k-2)/2}-2+a_{k-1}a_{k-2}\dots a_{k/2}-b^{(k-2)/2}+r\\=b^{k/2}+a_{k-1}a_{k-2}\dots a_{(k-1)/2}+O(1)=b^{k/2}+\frac{n}{b^{(k-1)/2}}+O(1)$$

So

$$g_b(n)=\frac{b^{k/2}+\frac{n}{b^{k/2}}}{\sqrt{n}}+O(\frac{1}{\sqrt n})=\frac{b^{k/2}}{\sqrt{n}}+\frac{\sqrt{n}}{b^{k/2}}+O(\frac{1}{\sqrt n})$$

Notice that $n$ is from $[b^{k-1},b^k]$, so $g_b(n)$ takes value from $[2+O(\frac{1}{\sqrt n}),\frac{1+b}{\sqrt{b}}+O(\frac{1}{\sqrt n})]$

Therefore, we can say that $\limsup g_b(n)\le \frac{1+b}{\sqrt{b}}$ and $\liminf g_b(n)\ge 2$. The "minimum" case achieved when $n=b^{2k}$, the "maximum" case achieved when $n=b^{2k+1}$. Thus, the problem is solved.