# Which number base contains the most Palindromic Numbers?

## Plotting Palindromic Numbers

I made a script that checks numbers through number bases and plots a black pixel if the number is a palindrome in the corresponding base.

If we check the first $256$ numbers (width) and first $256$ number bases (height), and draw a picture by starting in the upper left corner, we get the image on the left.

If we also connect all the $2$-digit palindromes with straight lines, we get the image on the right.

$\hspace{1.15cm}$ $\hspace{1cm}$

• The black triangle represents one-digit-palindromes.

• If we look at the $2$-digit-palindromes, they form straight lines.

• If we look at the $3$-digit-palindromes, they form parabolas. The first parabola is colored in yellow and located above the red lines as it can be seen on picture on the right.

In general, $D$-digit palindromes form a set of polynomials of degrees $D-1$. But it's not clear on which exact points on those curves the palindromes appear, except for the lines.

## Counting Palindromes

The thing that I'm interested in, is counting the palindromes outside the black-triangle-region, among $n$ first natural numbers.

If we count the palindromes among first $n$ numbers in all natural bases $b>1$, but ignore the one-digit-palindromes (ones that fill up the black triangle on the picture),

Which base $b$ will contain the most palindromes?

By computation,

Start counting at $n=1$, then the first palindrome occurs at number $3$ in base $2$.
Base $2$ will hold most palindromes until,

Base $3$ has most most palindromes at $n=26$,
Then base $2$ has most palindromes at $n=27$,
Then base $3$ has most palindromes at $n=28$,
Then base $2$ has most palindromes at $n=31$,
Until base $4$ takes the lead at $n=55$.

After that, all bases $b\ge5$ seem to follow an equation and overtake the lead when $n$ reaches:

$$b^3 - 2b^2 + 4b - 2$$

I checked this for bases up to $16$ and confirmed that $n$ follows the equation: (Starting at $b=5$)

$$93,166,271,414,601,838,1131,1486,1909,2406,2983,3646 \dots$$

With my computations so far, I would conjecture that this equation holds for all $b\ge5$

But this requires a proof.

It would be even better if someone can show how to arrive at this formula without relying on computation.

So far, Mastrem showed why the overtake happens at $b^3 - 2b^2 + 4b - 2$, which makes sense. But it is still not shown that it is the only, and the first, overtake that happens.

Deeper analysis of the plot can be found here.

• I guess if you only check numbers up to $n$ then the best you can do is just take base $n+1$, since then all numbers are single-digit and thus a palindrome. – vrugtehagel Apr 13 '17 at 20:38
• @vrugtehagel I'm not counting the single-digit palindromes as stated in the problem, since the task is trivial then. – Vepir Apr 13 '17 at 20:39
• Without thinking too much about it I would guess that a larger base implies more palindromes. Because a number $x$ that's a palindrome in base $b$ will also be a palindrome $y$ in base $b+1$, even though the values of $x$ and $y$ are different. For example, every possible palindromic string of zeros and ones in base 2 is also a palindromic string in base 3, even though they represent different numbers. Like $101$. $101$ in base 2 is 5 and $101$ in base 3 is 4. Different values but still a palindromic presentation. And a larger base means more digits to use means more palindromes to construct. – tilper Apr 13 '17 at 21:18
• @tilper: But the same palindromic string in a higher base may already be above the limit $n$. For example, if $n=6$, then $101$ is a valid palindrome in base $2$, but not in base $3$, as $10>6$. Also note that due to exclusion of single-digit palindromes, as bases $\ge n$ will automatically get the count $0$. – celtschk Apr 14 '17 at 11:08
• We can rewrite $b^3-2b^2+4b-2$ as $b.b^2-2b^2+3b+b-2=(b-2)b^2+3b+(b-2)$. This shows more clearly that the overtakes happen at $333_5, 434_6, 535_7$ etc. – nickgard Apr 14 '17 at 12:03

We have: $$b^3-2b^2+4b-2=(b-2)b^2+3b+(b-2)$$ and: $$b^3-2b^2+4b-2=(b-1)^3+(b-1)^2+3(b-1)+1$$ For all $b\in\mathbb{N}_{\ge 5}$, let $f(b)$ be the amount of palindromes in base $b$ up to and including $b^3-2b^2+4b-2$ and let $g(b)$ be the amount of palindromes in base $b-1$ up to and including $b^3-2b^2+4b-2$. Now, from the very first 'factorization', we see that: $$f(b)=(b-3)b+4+(b-1)=b^2-2b+3$$ Because, if a palindrome starts with a digit $1\le k\le b-3$, we can choose whatever digit we want for the middele one and when the palindrom starts with $b-2$, we have $4$ options for the middle digit. Also, we can choose a total of $b-1$ two digit palindromes.
Now for $g(b)$. We split this case up into $4$ digits and $3$ digits. If we have a $4$ digit number, the first digit is a $1$ and the second one is $1$ or $0$, so the only two options option are $1111_{b-1}$ and $1001_{b-1}$. All $3$ digit numbers are possible, a total amount of $(b-2)(b-1)$ numbers (because we can't choose $0$ as the leading digit). So when we also include the two digit palindromes: $$g(b)=2+(b-2)(b-1)+(b-2)=b^2-2b+2=f(b)-1$$ And since $b^3-2b^2+4b-2$ is a palindrome in base $b$, but not in base $b-1$, the base $b$ 'takes' over at $b^3-2b^2+4b-2$.
The thing I'm still trying to prove is that this is the first time $b$ 'takes over'. As soon as I know, I'll edit it in