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.

Solution 1:

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