Probability of being a palindrome?

Question

I often see how people points out that a certain number is a palindrome in some base, the implication being that it is somewhat a special number. Of course such considerations are rather subjective, but that made me wondering; is it the property of being a palindrome so rare? To be precise:

What is the probability that a given natural number $n$ is a palindrome in at least one base $b\in\{2,3,\ldots,10\}$? What about if we let $b\in\{2,3,\ldots,n-2\}$?

For those who might be bothered for the use of "probability that a given natural number": You can understand that I am asking about the natural density of palindromes, with the above precisions. I just stated the question as it is because I might content myself with some simulation or insight on the subject (the reason being that I haven't found much about this on the web and couldn't come up with an answer myself, so just in case it is harder than expected...), and because of future readers who might also be intrigued about this and don't know about natural density.

Answer 1

Well, if you look at some base $b$ and numbers that can be written in $n$ digits in that base, the number of such numbers is $b^n-b^{n-1}=(b-1)\,b^{n-1}$. Out of these, the number of palindromes is $$ (b-1)\,b^{\frac n2-1}\text{ if $n$ is even, and}\quad (b-1)\,b^{\frac{n+1}2-1}\text{ if $n$ is odd}. $$ (I am assuming you are interested in number that do not start with a "$0$"). This suggests densities relative to base $b$ of $$ \frac{(b-1)\,b^{\frac n2-1}}{(b-1)\,b^{n-1}}=\frac{1}{b^{\frac n2}} \text{ if $n$ is even, and}\quad \frac{(b-1)\,b^{\frac{n+1}2-1}}{(b-1)\,b^{n-1}}=\frac{1}{b^{\frac{n-1}2}} \text{ if $n$ is odd} $$ or: $$ \frac1{b^{\lfloor\frac n2\rfloor}}. $$

Of interest is the fact that these densities $\to0$.

Of course if you want to add up densities for several bases, you then have to worry about palindromes in several bases simultaneously, but the above expressions give you a good starting point / order of magnitude.

Answer 2

The density of numbers that aren't palindrome for some $b\in\{2,3,\cdots,n-2\}$ is smaller then the density of prime numbers which is $0$.That's because every such number must be a prime.

For the first by the formula A.G. provided if you sum the probabilities for $2,3,4,5,6,7,8,9,10$ you'll still get $0$ and that's if you overcount the palindromes that are also in other bases.

Answer 3

[I am just connecting the dots from the two answers I got to my two questions. Merits for the answer to the first question to @A.G., and for the second one to @kingW3.]

Case $b\in\{2,\ldots,10\}$: The answer is that the natural density is $0$; that is, imprecisely, that the probability of randomly picking a natural number which is a palindrome in at least one base $b\in\{2,\ldots,10\}$ is $0$.

Let's fix $b$. For $N\in\mathbb{N}$ let $j=j(N)\in\mathbb{N}$ be given by $b^j\leq N<b^{j+1}$. We have that \begin{align} \frac{\#\{\text{palindromes}_b\leq N\}}{N}\leq&\,\frac{\#\{\text{palindromes}_b\leq b^{j+1}\}}{b^j}\\ \leq&\,\frac{j\cdot\#\{\text{palindromes}_{b}\text{ with $j$ digits\}}}{b^j}\\ \leq&\,\frac{jb^{j/2}}{b^j},\\ \end{align} where the last inequality follows from A.G.'s answer, and the previous one from the fact that there are more palindromes in base $b$ in $\{b^{j},b^j+1,\ldots,b^{j+1}-1\}$ than in $\{b^k,b^k,\ldots,b^{k+1}-1\}$ if $k<j$. Letting $N\to\infty$ in the estimates above yields that the natural density of the palindromes in base $b$ is $0$, which implies the claim since the number of palindromes in base $\in\{2,\ldots,10\}$ is smaller than the sum of the palindromes in base $b$ over $b=2,\ldots,10$.

Case $b\in\{2,\ldots,n-2\}$: From kingW3's comments, the numbers $n$ which are non-palindromic in any base $b\in\{2,\ldots,n+2\}$ are called strictly non-palindromic. These numbers are all primes except for $0,1,4$ and $6$, which, since the natural density of the prime numbers is $0$, tells us that the natural density of the numbers $n$ which are palindromes in at least one base $b\in\{2,\ldots,n-2\}$ is $1$.